### 问题描述 有 $n$ 个小球排成一排，从左到右编号依次为 $1, 2, \cdots n$。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出： - `1 x`：从左到右移除小球。先移除最左侧的小球，随后每隔 $x-1$ 个小球移除一个小球，直到右侧没有更多需要移除的小球为止。若没有小球则什么也不做。 - `2 x`：从右到左移除小球。先移除最右侧的小球，随后每隔 $x-1$ 个小球移除一个小球，直到左侧没有更多需要移除的小球为止。若没有小球则什么也不做。 操作结束后将剩下的小球重新排成一排，所有未被移除的小球的相对位置不变。 你需要回答最后剩余的小球编号的第 $k$ 小是多少。如果剩余小球不足 $k$ 个，输出 $-1$。 ### 输入格式 输入第一行包含三个整数 $n, m, k$，分别表示初始时小球的总数，总操作次数和需要查询的小球编号在最后剩余的小球中的排名。 接下来 $m$ 行，每行两个整数 $op, x$，分别表示操作类型和操作参数。 ### 输出格式 输出一个整数，表示剩余的小球编号的第 $k$ 小。如果剩余小球不足 $k$ 个，输出 $-1$。 ### 样例输入 ```text 7 3 2 2 6 2 3 1 7 ``` ### 样例输出 ```text 5 ``` ### 说明 最初有 $7$ 个小球排成一排，从左到右编号分别为 $1, 2, 3, 4, 5, 6, 7$。 第一次操作从右到左，先移除了最右侧的 $7$ 号小球，然后跳过 $5$ 个小球，移除了 $1$ 号小球。此时左侧没有更多需要移除的小球，操作结束。此时剩余 $5$ 个小球，从左到右编号依次为 $2, 3, 4, 5, 6$。 第二次操作从右到左，先移除了最右侧的 $6$ 号小球，然后跳过 $2$ 个小球，移除了 $3$ 号小球。此时左侧没有更多需要移除的小球，操作结束。此时剩余 $3$ 个小球，从左到右编号依次为 $2, 4, 5$。 第三次操作从左到右，先移除了最左侧的 $2$ 号小球。此时右侧已经没有更多需要移除的小球，操作结束。此时剩余 $2$ 个小球，从左到右编号依次为 $4, 5$。 最后剩余的小球中编号第 $2$ 小为 $5$。 ### 评测数据规模 对于 $20$% 的评测数据，$2\leq n \leq 10^3，1\leq m \leq 10^3$。 对于 $40$% 的评测数据，$2\leq n \leq 10^5，1\leq m \leq 10^5$。 对于 $100$% 的评测数据，$2\leq n \leq 10^9，1\leq m \leq 2\times 10^5，1\leq k\leq n，1\leq op \leq 2，2\leq x\leq n$。