Side-Scrolling Field Theory¶
Estimated time limit: 0.5 seconds. Memory limit: 256 MB.
The actual time limit is twice the slowest-case median runtime of the reference solution on the target judge, rounded up to a multiple of \(0.5\) seconds. See the benchmark environment.
Story¶
There are \(N\) students in a side-scrolling field that wraps around horizontally. From our viewpoint, they stand in a row numbered \(1,\ldots,N\) from left to right. Each student either faces us or faces away, and interprets “left” and “right” relative to their own facing direction.
The students are playing a game of passing an object, initially held by student one. On each turn, the holder passes it to the student \(p\) positions to their own left or right; zero positions means the holder themselves. Since the field wraps around, \(p\) may exceed \(N\). Crossing the boundary where the ends meet does not change anyone's facing direction.
Each student has exactly one major, represented by an uppercase letter from A to Z. Different students may have the same major. There will be \(M\) transfers. After each transfer, print the major of the student holding the object.
Formal Problem Statement¶
From the observer's viewpoint, \(N\) students are numbered \(1,\ldots,N\) from left to right, with the right end connected to the left end. Student \(i\) has facing value \(f_i\) : zero means facing away from the observer, and one means facing the observer. Their major is represented by the uppercase letter \(C_i\) ; different students may have the same major.
Student one initially holds the object. Each operation gives \(d,p\) : zero means the holder's own left and one means their own right. Move \(p\) positions in that direction and pass the object to that student. Zero positions means the holder themselves, and a move may go around the row multiple times. Facing directions never change. Print the new holder's major after every operation.
An upward arrow means facing away from the observer below; a downward arrow means facing the observer. The chain of indices below shows the holder after each transfer.
Input Format¶
The first line contains integers \(N,M\) . Each of the next \(N\) lines contains an integer \(f_i\) and an uppercase letter \(C_i\) for student \(i\) . Each of the following \(M\) lines contains integers \(d,p\) describing a transfer.
Output Format¶
Print \(M\) lines, each containing the uppercase letter representing the holder's major after the corresponding transfer.
Samples¶
Sample 1¶
Input¶
5 5
0 A
1 B
0 C
1 D
1 E
1 0
1 6
1 6
0 6
1 2
Output¶
A
B
A
E
C
Sample 2¶
Input¶
1 3
1 Z
0 0
1 1000000000
0 1
Output¶
Z
Z
Z
Sample Explanation¶
In Sample 1, the successive holders are students one, two, one, five, and three. Left and right are determined by the current holder. Sample 2 has only one student, who keeps the object after every transfer.
Constraints and Guarantees¶
For 100% of the data: \(1\le N,M\le30000\) , \(f_i,d\in\{0,1\}\) , \(0\le p\le10^9\) , and every \(C_i\) is an uppercase English letter.
“No move crosses an end” means that the index stays between one and \(N\) throughout each move before any wrapping. The total step count is the sum of all \(p\) values in one input file.
| Score share | Additional conditions |
|---|---|
| 50% | Total step count at most \(4000000\) ; no move crosses an end |
| 20% | Total step count at most \(4000000\) |
| 30% | None |