Railroads
本题没有可用的提交语言。
Description
There are $n$ train stations numbered from $1$ to $n$. For each station there are two one-way outgoing railroad connections. From the $i$-th station each outgoing railroad connection can go to one of these destinations:
- the $1$-st station;
- the $(i + 1)$-th station, if $i < n$.
You are responsible for evaluating the route of an automated train on these railroads. During one run the automated train keeps count of how many times it has visited each station. If the train has visited the current station an odd number of times, it will use the first outgoing railroad connection, otherwise it will use the second outgoing railroad connection.
You have been given a list of $q$ possible runs of the train, for each run you have been given the start station and how many times the train goes to the next station. The train considers the start station visited for its routing. For each run you need to find the station number where the train will stop.
The first line contains an integer $n$ $(1 \leq n \leq 2 \cdot 10^5)$, the number of stations. The next two lines each contains a length $n$ symbol sequence consisting of the symbols "<" and ">". The first line represents the first outgoing connection from each station, the second line represents the second outgoing connection from each station. The $i$-th symbol in these sequences describes the outgoing connection from the $i$-th station, with ">" representing a connection to the $(i+1)$-th station, and "<" to the $1$-st station. It is guaranteed that the last symbol in both sequences will be "<".
The following line contains an integer $q$ $(1 \leq q \leq 2 \cdot 10^5)$, the number of runs to be queried. Then follow $q$ lines each representing a run of the automated train. In each line there are two space separated integers: the starting station number $s$ $(1 \leq s \leq n)$ and the number of times the train will go to the next station $l$ $(1 \leq l \leq 10^{18})$.
Output $q$ lines with a single integer each – for each queried run of the automated train output the station number where the train will stop.
Input
The first line contains an integer $n$ $(1 \leq n \leq 2 \cdot 10^5)$, the number of stations. The next two lines each contains a length $n$ symbol sequence consisting of the symbols "<" and ">". The first line represents the first outgoing connection from each station, the second line represents the second outgoing connection from each station. The $i$-th symbol in these sequences describes the outgoing connection from the $i$-th station, with ">" representing a connection to the $(i+1)$-th station, and "<" to the $1$-st station. It is guaranteed that the last symbol in both sequences will be "<".
The following line contains an integer $q$ $(1 \leq q \leq 2 \cdot 10^5)$, the number of runs to be queried. Then follow $q$ lines each representing a run of the automated train. In each line there are two space separated integers: the starting station number $s$ $(1 \leq s \leq n)$ and the number of times the train will go to the next station $l$ $(1 \leq l \leq 10^{18})$.
Output
Output $q$ lines with a single integer each – for each queried run of the automated train output the station number where the train will stop.
12
>>>><><><>><
><>>>><>><><
3
1 1
4 7
8 14
2
<<
<<
2
1 3
2 3
2
6
6
1
1