스플릿스트림

스플릿스트림 시스템은 유한한 수열을 처리하는, 순환이 없는 노드들의 네트워크다. 노드에는 두 종류가 있다 (그림 J.1 참고).

분기(split) 노드는 수열 하나를 입력으로 받아 두 출력에 번갈아 나눠 보낸다. 첫 번째 수는 출력 1, 두 번째 수는 출력 2, 세 번째 수는 다시 출력 1로 간다.

병합(merge) 노드는 두 입력 수열을 받아 번갈아 합쳐 하나의 출력을 만든다. 출력은 입력 1의 첫 번째 수, 입력 2의 첫 번째 수, 입력 1의 두 번째 수, 입력 2의 두 번째 수 순서로 이어진다. 한쪽 입력이 더 짧으면, 짧은 쪽이 끝난 뒤 긴 쪽에 남은 수는 합쳐지지 않고 그대로 이어서 출력된다.

그림 J.1: 분기 노드와 병합 노드의 동작 방식.

네트워크의 입력은 양의 정수 1, 2, 3, ..., m으로 이루어진 수열 하나다. 모든 노드의 모든 출력은 질의할 수 있다. 질의는 주어진 출력의 수열에서 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에 대해 출력 x의 수열에서 k번째 수를 한 줄에 출력한다. 그러한 원소가 없으면 none을 출력한다.