Color game

Vasya plays an intricate game. Several circles with colored points (each circle have the same number of points) lies before him. Note that circles themselves are located around the circle. All circles are numbered from 1 to N and points on these circles – from 1 to M. Each point is colored in one of 30 colors.

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

1. Let the token be in the circle C at the point with the number P.

2. Let S be the number of points of different colors in the K-neighborhood of P-point on the circle C, i.e. on the segment [P-K, P+K]. Note that the segment is located on the circle, so point M is followed by point 1. For example, if M = 6, P = 5, K = 2, then the segment is [P-2, P+2], which breaks down to [3, 6] and [1, 1].

3. Move the token to the circle (N-C+1)+S at the point P+S. Note that circlesthemselves are located around the circle and circle N is followed by circle 1.

Vasya wants to find out at which circle and point token will be after all the trick moves.

Consider an example. Let N = 5, M = 4, K = 1. The example uses only two colors: black and white. The dotted lines on the picture denote the neighborhood of the points at which the token was.

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

For a given set of circles and the number T you are to find where the token will be after T moves.

Note, that given circles have one feature – for i = 1,2, ..., N-1 circle i differs from the circle i+1 in at most one point.

Input

The first line contains four numbers N, M, T, K. The second line contains M integers – the colors of points on the first circle. Each color is an integer ranging from 0 to 29.

The next N-1 rows consist of difference between successive circles: the row i describes the difference between the circle i and circle i+1 – a pair of numbers P_i, Color_{i+1} – the point at which the circles different and color of the point for the circle i+1.

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

Output

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

Examples