题目描述

小依喜欢随机游走，不过又希望没有那么随机的游走。

现在有一排 $n$ 个建筑，编号为 $1, 2, \cdots, n$。编号相邻的建筑是相邻的。小依有两种随机游走的策略，用字符串 $x _ 1$ 和 $x _ 2$ 表示，其每个字符都是 < 或者 >。如果采取 < 的游走策略，那么小依会回到 $1$ 号建筑；如果采取 > 的游走策略，小依会游走到当前建筑编号加一的建筑。为了不走出这一排建筑，保证 $x _ {1, n}$ 和 $x _ {2, n}$ 都是 <。

对于一个建筑而言，当这里来过的次数是奇数（包含这次）时，采取第一种策略。否则采取第二种策略。

现在小依有 $q$ 个游走的计划，每次都是从某个点 $p$ 开始，游走 $k$ 次。小依想知道对于这 $q$ 个游走的计划，如果实行了的话，最后会游走到哪里呢？

注意，这只是计划，并没有真的游走。所以来过某个建筑的次数只用考虑当前计划内的次数。

输入格式

第一行一个正整数 $n$。

接下来两行，各一个字符串，表示 $x _ 1$ 和 $x _ 2$。

接下来一行一个正整数 $q$。

接下来 $q$ 行，每行两个正整数 $p, k$，表示一次游走计划。

输出格式

共 $q$ 行，每行一个正整数，表示最后会游走到的建筑编号。

样例

样例输入 1

10
>>>>>>>>><
>>>><>>>><
10
10 17
5 20
6 10
7 1
6 16
7 18
1 18
6 19
1 19
9 2

样例输出 1

2
10
6
8
2
5
4
5
5
1

样例输入/输出 2

见下发文件 walk2.in/ans。该样例满足测试点 $1 \sim 2$ 的限制。

样例输入/输出 3

见下发文件 walk3.in/ans。该样例满足测试点 $12$ 的限制。

样例输入/输出 4

见下发文件 walk4.in/ans。该样例满足测试点 $16 \sim 18$ 的限制。

样例输入/输出 5

见下发文件 walk5.in/ans。该样例满足测试点 $22 \sim 25$ 的限制。

数据范围与提示

本题共 $25$ 个测试点，每个测试点 $4$ 分。

• 特殊性质 A：$\sum k \le 10 ^ 7$。
• 特殊性质 B：不存在一个 $i$，使得 $x _ {1, i} = x _ {2, i} = \texttt >$。
• 特殊性质 C：不存在一个 $i$，使得 $x _ {1, i} = \texttt <$，而 $x _ {2, i} = \texttt >$。
• 特殊性质 D：不存在一个 $i$，使得 $x _ {1, i} = \texttt >$，而 $x _ {2, i} = \texttt <$。
• 特殊性质 E：保证对于所有计划，出发点 $p = 1$。

对于所有数据，$1 \le n, q \le 3\times 10 ^ 5$，$1 \le p \le n$，$1 \le k \le 10 ^ {18}$。