Color game#2557

Color game

2 seconds
64 megabytes
Very hard

Vasya plays an intricate game. In front of him are several circles with colored points, and each circle has the same number of points. Note that the circles themselves are arranged in a circle. All circles are numbered from to , and the points on these circles are numbered from to . Each point is colored in one of colors.

Initially, Vasya puts a token on the first point of the first circle. Then he moves the token times as follows:

  1. Let the token be in circle at the point numbered .

  2. Let be the number of different colors among the points in the -neighborhood of point on circle , that is, on the segment [P-K, P+K]. Note that the segment wraps around the circle, so point is followed by point . For example, if M = 6, P = 5, K = 2, then the segment [P-2, P+2] consists of points and .

  3. Move the token to circle (N-C+1)+S at point P+S. Note that the circles themselves are arranged in a circle, and after circle comes circle .

Vasya wants to determine, after all these moves, on which circle and at which point the token will be.

Consider an example. Let N = 5, M = 4, K = 1. In this example, only two colors are used: black and white. The dotted lines in the picture show the neighborhoods of the points where the token was.

Initially, C = 1, P = 1. In the -neighborhood there are both colors, that is S = 2. Hence, C' = (5-1+1)+2=2, P' = 1+2 = 3. At this new position, the -neighborhood contains only white color, so S = 1. C''=(5-2+1)+1=5, P''=3+1=4. Finally, in the next-to-last position, the -neighborhood contains both colors, S = 2, C'''=(5-5+1)+2=3, P'''=4+2=2.

Given a set of circles and the number , find where the token will be after moves.

Note that the given circles have the following property: for i = 1, 2, \ldots, N-1, circle differs from circle i+1 in at most one point.

Input

The first line contains four numbers: , , , . The second line contains integers— the colors of the points on the first circle. Each color is an integer in the range from to .

The next N-1 lines describe the differences between consecutive circles: the -th line describes the difference between circle and circle i+1 as a pair P_i, \text{Color}_{i+1} — the point where the circles differ, and the color of this point for circle i+1.

1 \le N \le 50000, 1 \le T, M \le 100000, 0 \le K < M/2.

Output

The output should contain a pair of numbers — the number of the circle and the number of the point — the position of the token after moves.

Examples

Example 1

Loading
Loading