У Миши есть ориентированный граф из $$$n$$$ вершин. Из каждой вершины графа выходит ровно два ребра — синее и красное. Папа Миши увидел этот граф и придумал $$$q$$$ маршрутов.
Каждый маршрут задается номером начальной вершины $$$v$$$ и состоит из перемещений. Перемещения состоят из переходов и задаются строкой $$$s$$$.
Строка $$$s$$$ формируется по следующим правилам:
Например, маршрут, начинающийся в вершине $$$529$$$ и состоящий из $$$79854$$$ перемещений, каждое из которых требует совершить переходы по синему-красному-красному-синему рёбрам, опишется следующим вводом:
Теперь Мише предстоит определить, в какой вершине завершится каждый маршрут. Вам необходимо ему в этом помочь.
В первой строке записаны два целых числа $$$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$$$ строк содержат описания маршрута в таком виде:
Выведите в отдельных строках $$$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
