Statement is not available in English language
H. Красно-синие маршруты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Миши есть ориентированный граф из $$$n$$$ вершин. Из каждой вершины графа выходит ровно два ребра — синее и красное. Папа Миши увидел этот граф и придумал $$$q$$$ маршрутов.

Каждый маршрут задается номером начальной вершины $$$v$$$ и состоит из перемещений. Перемещения состоят из переходов и задаются строкой $$$s$$$.

Строка $$$s$$$ формируется по следующим правилам:

  • Длина строки в точности равна $$$9$$$
  • От $$$1$$$ до $$$8$$$ первых символов строки являются цифрами и задают количество перемещений — число $$$M$$$ (не имеет ведущих нулей).
  • Оставшиеся позиции занимают символы «$$$R$$$» и «$$$B$$$», описывающие переходы в рамках одного перемещения — символ «$$$R$$$» задаёт переход по красному ребру, символ «$$$B$$$» задаёт переход по синему ребру.

Например, маршрут, начинающийся в вершине $$$529$$$ и состоящий из $$$79854$$$ перемещений, каждое из которых требует совершить переходы по синему-красному-красному-синему рёбрам, опишется следующим вводом:

  • $$$529$$$ $$$79854BRRB$$$

Теперь Мише предстоит определить, в какой вершине завершится каждый маршрут. Вам необходимо ему в этом помочь.

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$q$$$ $$$(2 \le n \le 10^5$$$, $$$1 \le q \le 5 \cdot 10^4)$$$ — количество вершин графа и количество маршрутов.

Во второй строке записаны $$$n$$$ целых чисел $$$r_1,r_2,\dots,r_n$$$ ($$$1 \le r_i \le n$$$), где $$$r_i$$$ — номер вершины, в которую ведёт красное ребро из вершины $$$i$$$.

В третьей строке записаны $$$n$$$ целых чисел $$$b_1,b_2,\dots,b_n$$$ ($$$1 \le b_i \le n$$$), где $$$b_i$$$ — номер вершины, в которую ведёт синее ребро из вершины $$$i$$$.

Следующие $$$q$$$ строк содержат описания маршрута в таком виде:

  • $$$v$$$ $$$s$$$ $$$(1 \le v \le n)$$$ — начальная вершина маршрута и строка, задающая перемещения по маршруту.
Выходные данные

Выведите в отдельных строках $$$q$$$ целых чисел $$$f_1,f_2,\dots,f_q$$$ — номера конечных вершины каждого из маршрутов

Пример
Входные данные
4 3
2 3 4 1
4 1 2 3
1 1RRRRRRRR
1 12345RBRB
1 10000001R
Выходные данные
1
1
2