在这个问题中，你需要从一个棋盘格的一个角移动到对角，同时遵循一定的规则并尽量减少移动次数。

在一个平面上有一个由 $m$ 行 $n$ 列组成的棋盘格。每个格子包含三种物品之一：石头、布或剪刀。我们从格子 $(1, 1)$ 出发，希望通过一系列移动到达格子 $(m, n)$。单次移动是指跳到距离当前格子不超过 $d$ 的任意格子。距离是按格子中心计算的：格子 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离为 $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$。此外，每次移动必须到达一个包含能击败前一个格子中物品的物品的格子。正如“石头、剪刀、布”游戏一样，石头击败剪刀，剪刀击败布，布击败石头。当我们到达一个格子时，我们会取走该格子中的物品，因此禁止重复访问同一个格子。

由于棋盘很大，其格子中物品的类型由随机数生成器决定，更准确地说是线性同余生成器。该生成器有一个状态，是一个 $0$ 到 $2^{32} - 1$ 之间的整数 $s$。为了获得 $0$ 到 $r - 1$ 之间的下一个随机数，我们执行赋值 $s := (s \cdot 1\,664\,525 + 1\,013\,904\,223) \pmod{2^{32}}$ 并返回 $s$ 除以 $r$ 的余数。初始的 $s$ 值在输入中给出。

格子中的物品按以下方式确定。对于每个格子，我们从集合 $\{0, 1, 2\}$ 中获取下一个随机数（即 $r = 3$）。如果该数字为 $0$，则物品为石头；如果为 $1$，则为布；如果为 $2$，则为剪刀。格子按从上到下的行顺序考虑，同一行中的格子按从左到右的顺序考虑。因此，格子的顺序如下：$(1, 1), (1, 2), \dots, (1, n), (2, 1), (2, 2), \dots, (2, n), \dots, (m, 1), (m, 2), \dots, (m, n)$。

一个重要的附加要求是，我们完成路径的时间不得超过以最大速度的一半沿直线从格子 $(1, 1)$ 到格子 $(m, n)$ 所需的时间，再加上三次额外移动。形式上，移动次数 $k$ 不得超过实数 $2 \cdot \frac{\sqrt{(m-1)^2+(n-1)^2}}{d} + 3$。

给定棋盘的尺寸、单次移动的最大距离以及随机数生成器的初始状态，请找到一条满足所有约束的路径。

输入格式

输入的第一行包含空格分隔的整数 $m, n, d$ 和 $s$：棋盘的高度和宽度、单次移动的最大距离以及随机数生成器的初始状态 ($100 \le m, n \le 2^{16}, 10 \le d \le 100, 0 \le s \le 2^{32} - 1$)。注意，$m, n$ 和 $d$ 的下界相当大。

输出格式

在第一行，输出你找到的路径中的移动次数 $k$。在接下来的 $(k+1)$ 行中，按遍历顺序输出所访问格子的坐标。先输出行号，再输出列号。

路径的第一个格子必须是 $(1, 1)$，最后一个格子必须是 $(m, n)$。每个格子最多只能访问一次。路径中每两个连续格子之间的距离不得超过 $d$，且总移动次数 $k$ 不得超过实数 $2 \cdot \frac{\sqrt{(m-1)^2+(n-1)^2}}{d} + 3$。

如果存在多条可能的路径，输出其中任意一条即可。题目保证在所有评测数据中，都存在一条满足所有约束且长度不超过 $1.5 \cdot \frac{\sqrt{(m-1)^2+(n-1)^2}}{d} + 3$ 的路径。

样例

输入 1

100 120 50 5

输出 1

5
1 1
31 41
59 70
92 107
98 120
100 120

说明

下表包含了样例中访问过的格子的 $s$ 值和物品信息。

分数 $\frac{\sqrt{(m-1)^2+(n-1)^2}}{d}$ 的值为 $3.0959 \dots$，因此在本例中，要求移动次数不超过 $9$ 次，且评测保证存在一条 $7$ 次或更少移动的路径。