Rock-Paper-Scissors on a Plane

In this problem, you have to travel from one corner of a checkered field to the opposite corner conforming to certain rules and avoiding making too much moves.

There is a checkered field on a plane consisting of m rows and n columns. Each cell of the field contains one of three items: rock, paper or scissors. We start moving from the cell (1, 1) and want to reach the cell (m, n) by performing a sequence of moves. A single move consists of jumping into any cell that is no farther than d from the current cell. The distance is measured between cell centers: the distance between cells (x_1, y_1) and (x_2, y_2) is . Additionally, each move must lead to a cell containing an item which defeats the item on the previous cell. As in the game “Rock-Paper-Scissors”, rock defeats scissors, scissors defeat paper, and paper defeats rock. When we arrive at a cell, we take the item from that cell, so it is forbidden to visit a single cell twice.

The field is fairly large, so the types of items in its cells are determined by use of a random number generator, more precisely, a linear congruential generator. This generator has a state which is an integer s from 0 to 2^32 - 1. In order to obtain the next random number from 0 to r - 1, we carry out the assignment s := (s ∙ 1 664 525 + 1 013 904 223) mod 2^32 and return the remainder of dividing s by r. The initial value of s is given in the input.

The items in the cells are determined in the following way. For each cell, we obtain the next random number from the set {0, 1, 2} (that is, r = 3). If this number is a zero, the item is rock, if it is one, paper, and in case it is two, scissors. Cells are considered row-by-row from top to bottom, cells in one row are considered from left to right. So, the order of cells is the following: (1, 1), (1, 2), ... , (1, n), (2, 1), (2, 2), ... , (2, n), ... , (m, 1), (m, 2), ... , (m, n).

An important additional requirement is that we must finish in time no greater than the time it would take to travel from cell (1, 1) to cell (m, n) along a straight line with half the maximum speed, plus three extra moves. Formally, the number of moves must not exceed the real number .

Given the dimensions of the field, the maximum travel distance for a single move and the initial state of the random number generator, find a path satisfying all the constraints.

Input

The first line contains integers m, n, d and s separated by spaces: the height and width of the field, the maximum travel distance for a single move and the initial state of the random number generator (100 ≤ m, n ≤ 2^16, 10 ≤ d ≤ 100, 0 ≤ s ≤ 2^32 - 1). Note that the lower bounds for the numbers m, n and d are fairly large.

Output

On the first line, print the number of moves k in the path you found. In the next (k + 1) lines, print the coordinates of the visited cells in the order of traversal. Print the row first and the column second.

The first cell must be (1, 1), and the last one must be (m, n). Each cell may be visited at most once. The item in each next cell must defeat the item in the previous cell. The distance between any two consecutive cells of the path must not exceed d, and the total number of moves k must not exceed the real number .

If there are several possible paths, print any one of them. It is guaranteed that in all the judges tests, there exists a path satisfying all constraints with length not exceeding the real number .

Examples

Note

The following table contains the values of s and the items for the cells visited in the example.

The value of the fraction is 3.0959..., so in this example, it is required to make no more than nine moves, and the judges formally guarantee that there exists a path consisting of seven moves or less.