E. Life as a Monster
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

In a kingdom there are N people. The i-th person lives on a point (xi, yi). You are a monster that needs to go around the kingdom and capture all N people.

  • You start at some point (u, v)
  • In 1 second, you can move from point (u, v) to point (u’, v’) where |u’ - u| ≤ 1 and |v’ - v| ≤ 1. This means in 1 second you can move to 8 neighboring points. You can also stay at the same position (which is pointless).

Your journey will be like this:

  • You start from (u, v)
  • You go to the 1st person at (x1, y1), instantly capture him.
  • Then you need to go back to your home, and rest for 2 seconds.
  • Then you go to the 2nd person at (x2, y2), instantly capture him.
  • Then you need to go back to your home, and rest for 2 seconds.
  • This repeats until you capture all N people.

You have to process Q queries of 2 types:

  • 0 – The i-th person move to some new point (xi’, yi’).
  • 1 – If you start at point (u, v), what is the minimum time to complete your journey?

In this problem, you will be given integer BASE and multiple queries. You will have to set the initial value T = 0.

Query of type 0 means that the specified person moves to the point ((a1 * T + b1)%BASE, (a2 * T + b2)%BASE).

For query of type 1 you will need to output the minimum time of your journey of capturing all the people, if you would start at the coordinate ((a1 * T + b1)%BASE, (a2 * T + b2)%BASE). You should update the value of T with the calculated time.

Input

In the first line of input there are three integers N, Q and BASE (0 ≤ N, Q ≤ 105, 0 ≤ BASE ≤ 109. In the following N lines there are two integers xi and yi each (0 ≤ xi, yi ≤ BASE) – coordinates of the people.

In the following Q lines there are queries of the following types:

  • 0 i a1 b1 a2 b2
  • 1 a1 b1 a2 b2
Where i is the index of the person (1 ≤ i ≤ N) and a1, b1, a2, b2 are the values mentioned before (0 ≤ a1, b1, a2, b2 ≤ 109).
Output

For the every query of type 1 output single integer – the minimal time it would take to complete a journey of capturing all the people – each on separate line.

Examples
Input
3 4 1000000000
2 2
3 1
7 0
1 2 4 3 5
0 3 1 1 7 3
1 4 3 2 6
0 2 2 7 4 1
Output
28
728
Note

In the sample test case, you process four queries:

  1. You calculate the minimal time of journey starting at (4, 5). The answer is 28. You output the answer and update the value T = 28;
  2. The 3rd person moves to (29, 199);
  3. You calculate the minimal time of journey starting at (115, 62). The answer is 728. You output the answer and update the value T = 728;
  4. The 2nd person moves to (1463, 2913);