Hệ thống tách dòng là một mạng nút không có chu trình, xử lý các dãy số hữu hạn. Có hai loại nút (minh họa trong Hình J.1):

• Nút tách nhận một dãy số và phân phối luân phiên các số đến hai đầu ra. Số thứ nhất đến đầu ra 1, số thứ hai đến đầu ra 2, số thứ ba đến đầu ra 1, số thứ tư đến đầu ra 2, và cứ thế theo thứ tự này.
• Nút gộp nhận hai dãy số rồi xen kẽ chúng để tạo thành đầu ra duy nhất. Đầu ra chứa số thứ nhất của đầu vào 1, rồi số thứ nhất của đầu vào 2, số thứ hai của đầu vào 1, số thứ hai của đầu vào 2, và cứ thế. Nếu một dãy đầu vào ngắn hơn dãy còn lại, sau khi dùng hết dãy ngắn hơn, các số còn lại của dãy dài hơn được truyền trực tiếp mà không xen kẽ nữa.

Châu thổ Ganga-Brahmaputra (ESA, CC BY-SA 3.0 IGO)

Hình J.1: Minh họa cách hoạt động của nút tách và nút gộp.

Toàn bộ mạng có một đầu vào là dãy số nguyên dương $1,2,3,\ldots,m$. Có thể truy vấn bất kỳ đầu ra nào của bất kỳ nút nào. Một truy vấn tìm số thứ $k$ trong dãy của một đầu ra cho trước với $k$ cho trước. Nhiệm vụ của bạn là thực hiện các truy vấn này một cách hiệu quả.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $m$, $n$ và $q$, trong đó $m$ ($1 \le m \le 10^9$) là độ dài dãy đầu vào, $n$ ($1 \le n \le 10^4$) là số nút, và $q$ ($1 \le q \le 10^3$) là số truy vấn.

Tiếp theo là $n$ dòng mô tả mạng, mỗi dòng một nút. Nút tách có dạng S x y z, trong đó $x$, $y$, $z$ lần lượt định danh đầu vào, đầu ra thứ nhất và đầu ra thứ hai. Nút gộp có dạng M x y z, trong đó $x$, $y$, $z$ lần lượt định danh đầu vào thứ nhất, đầu vào thứ hai và đầu ra. Các định danh $x$, $y$, $z$ là những số nguyên dương khác nhau. Đầu vào toàn mạng có định danh $1$, còn các định danh đầu vào/đầu ra khác tạo thành một dãy liên tiếp bắt đầu từ $2$. Mỗi định danh đầu vào trừ $1$ xuất hiện như đúng một đầu ra. Mỗi định danh đầu ra xuất hiện như đầu vào của nhiều nhất một nút.

Mỗi dòng trong $q$ dòng tiếp theo mô tả một truy vấn. Mỗi truy vấn gồm hai số nguyên $x$ và $k$, trong đó $x$ ($2 \le x \le 10^5$) là định danh đầu ra hợp lệ và $k$ ($1 \le k \le 10^9$) là chỉ số của số cần tìm trong dãy đó. Chỉ số trong dãy bắt đầu từ $1$.

Dữ liệu ra

Với mỗi truy vấn $x$ và $k$, in một dòng chứa số thứ $k$ của dãy đầu ra có định danh $x$, hoặc none nếu không có phần tử mang chỉ số đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

100
99

Dữ liệu vào 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

Dữ liệu ra 2

47
98
49
51
53
100

Dữ liệu vào 3

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

Dữ liệu ra 3

2
none
none