Система разделения потоков — это ациклическая сеть узлов, обрабатывающая конечные последовательности чисел. Есть два типа узлов (показаны на рисунке J.1):

• Разделяющий узел получает последовательность чисел и поочерёдно распределяет их между двумя выходами. Первое число идёт на выход 1, второе — на выход 2, третье — на выход 1, четвёртое — на выход 2 и так далее в этом порядке.
• Объединяющий узел получает две последовательности чисел и чередует их элементы, формируя единственный выход. Он содержит первое число входа 1, затем первое число входа 2, второе число входа 1, второе число входа 2 и так далее. Если одна входная последовательность короче другой, после её исчерпания оставшиеся числа более длинной последовательности просто передаются без чередования.

Дельта Ganga-Brahmaputra (ESA, CC BY-SA 3.0 IGO)

Рисунок J.1: Иллюстрация работы разделяющих и объединяющих узлов.

У всей сети один вход: последовательность положительных целых чисел $1,2,3,\ldots,m$. Можно запрашивать любой выход любого узла. Запрос определяет $k$-е число последовательности для заданного выхода и заданного $k$. Ваша задача — эффективно реализовать такие запросы.

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

Первая строка содержит три целых числа $m$, $n$ и $q$, где $m$ ($1 \le m \le 10^9$) — длина входной последовательности, $n$ ($1 \le n \le 10^4$) — число узлов, а $q$ ($1 \le q \le 10^3$) — число запросов.

Следующие $n$ строк описывают сеть, по одному узлу в строке. Разделяющий узел имеет формат S x y z, где $x$, $y$ и $z$ обозначают соответственно его вход, первый выход и второй выход. Объединяющий узел имеет формат M x y z, где $x$, $y$ и $z$ обозначают соответственно первый вход, второй вход и выход. Идентификаторы $x$, $y$ и $z$ — различные положительные целые числа. Общий вход обозначен $1$, а остальные идентификаторы входов/выходов образуют последовательность подряд идущих чисел начиная с $2$. Каждый идентификатор входа, кроме $1$, встречается как ровно один выход. Каждый идентификатор выхода встречается как вход не более одного узла.

Каждая из следующих $q$ строк описывает запрос. Он состоит из двух целых чисел $x$ и $k$, где $x$ ($2 \le x \le 10^5$) — допустимый идентификатор выхода, а $k$ ($1 \le k \le 10^9$) — индекс искомого числа в этой последовательности. Индексация начинается с $1$.

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

Для каждого запроса $x$ и $k$ выведите в отдельной строке $k$-е число выходной последовательности с идентификатором $x$ или none, если элемента с таким индексом нет.

Примеры

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

200 2 2
S 1 2 3
M 3 2 4
4 99
4 100

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

100
99

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

100 3 6
S 1 4 2
S 2 3 5
M 3 4 6
6 48
6 49
6 50
6 51
6 52
5 25

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

47
98
49
51
53
100

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

2 3 3
S 1 2 3
S 3 4 5
M 5 2 6
3 1
5 1
6 2

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

2
none
none