[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

In the kingdom of Nlogonia there is a lake known as the "Big O" because of its perfectly round shape. On the side of this lake there are N houses, each of them a distance of one nlogonic unit apart from its neighbors. The houses are numbered from 1 to N in clockwise order, as can be seen in the following figure for N = 8.

In this way, if i < j the distance in clockwise order from house i to house j is j-i, whereas the corresponding distance in counterclockwise order is N - j + i. Note that the distance from a house to itself is N in both directions.

It is well known that the people of Nlogonia are avid football fans, so when a family moves to a house on the side of the lake it is very important for them to know who are their closest neighbors that follow the same team as they do. This is not always easy, since there may be many houses around the lake, many different football teams in Nlogonia, and a lot of moving around. Given a sequence of M movings, people who live on the shore of the lake want to welcome each new family arriving by telling them the distance from their new home to the closest houses that follow the same team as they do, both in clockwise and counterclockwise order. Note that if there is no other house on the shore of the lake whose family follows the same team as the newly arrived, said distance shall be N in both directions, as the closest house would in fact be the same house involved in the moving. Do you want to take part in the welcoming committee?

In Nlogonia there are F football teams, identified by different integer numbers from 0 to F-1. Because we don't want you to waste any time going from door to door asking which team is followed in each house, we will assume that initially the family living in house number i is a fan of team number e_i, being this number generated in pseudo-random fashion by the recursive formula

e₁ = A     and     e_i = (B × e_i-1 + C) mod F     for     i = 2, 3, ..., N

where A, B and C are constants and the expression x mod y represents the remainder of the integer division of x by y.

Input

The first line contains two integer numbers N and F, respectively indicating the number of houses around the lake and the number of football teams in Nlogonia (3 ≤ N ≤ 10⁵ and 1 ≤ F ≤ 10⁶). The second line contains three integer numbers A, B and C, which determine which team is followed by the families initially living around the lake as is described in the problem statement (0 ≤ A, B, C < F).

The third line contains a single integer number M, representing the number of movings that will be happening (1 ≤ M ≤ 10⁵). Each of the following M lines describes a moving using two integer numbers I and E, meaning that a family following team E is moving to house number I (1 ≤ I ≤ N and 0 ≤ E < F). The movings appear in the order that they occur, and should be taken into account by the committee for further welcomings.

Output

Print M lines, the i-th of them indicating the result of the i-th moving described in the input. Each line should contain two integer numbers d_ccw and d_cw, representing the distances in nlogonic units from the house involved in the moving to the first house whose family follows the same team, in counterclockwise and clockwise order respectively.

Example

Input:
5 10
1 1 1
6
1 1
2 2
3 1
4 2
5 1
3 1

Output:
5 5
5 5
2 3
2 3
2 1
2 2