34755번 - 기열과 쿼리

문제

본 병장이 군대에서 지켜야 할 중요한 문화, 기열에 대해 설명하겠다. 군대는 $N$명의 군인으로 이루어져 있으며, 각 군인은 계급, 명예, 그리고 고유한 군번을 가진다. 군번은 1ドル$부터 $N$까지 겹치지 않게 부여되며, 계급과 명예는 값이 클수록 높다. 군대에서는 계급과 명예를 바탕으로 맞선임 관계가 정의되며, 모든 군인은 기열 문화를 따라야 한다.

각 군인에게 1명 또는 0명 존재하는 맞선임은 다음과 같이 결정된다.

• 계급이 자신과 동일한 군인 중에서, 명예가 자신보다 높으면서 가장 낮은 명예를 가진 군인을 맞선임으로 삼는다.
• 만약 위 조건에 해당하는 군인이 없다면, 계급이 자신보다 높으면서 현재 존재하는 가장 낮은 계급을 가진 군인 중 가장 낮은 명예를 가진 군인을 맞선임으로 삼는다.
• 맞선임 조건에 부합하는 군인이 여러 명일 경우, 그중 군번이 가장 큰 군인이 맞선임이 된다.
• 계급과 명예가 모두 자신과 동일한 군인은 맞선임이 될 수 없다. 이는 동기 관계로 간주한다.
• 맞선임이 없는 경우, 맞선임은 존재하지 않는다.

기열 문화를 알려주겠다. 기열은 군인들에게 부과되는 의식으로, 다음과 같은 규칙을 따른다.

• 군인은 자신의 명예 값의 절반을 맞선임에게 바쳐야 한다. 이 과정에서 명예는 항상 정수로 유지되며 소수점은 버림 처리된다.
• 예를 들어, 명예가 9ドル$인 군인 안지민과 그의 맞선임 장성혁(명예 12ドル,ドル 계급 4ドル$로 안지민과 동일)이 있다고 하자. 안지민이 기열을 수행하면 $\lfloor 9/2\rfloor =4$의 명예를 장성혁에게 바친다. 이에 따라 안지민의 명예는 9ドル-4=5$가 되고, 장성혁의 명예는 12ドル+4=16$이 된다.
• 맞선임이 없는 경우, 군인은 자신의 명예 값에서 절반을 버림 처리한 값을 빼며, 군대의 자비로운 정책에 따라 소수점은 버림 처리된다. 예를 들어, 명예가 9ドル$인 군인이 맞선임 없이 기열을 수행하면 $\lfloor 9/2\rfloor =4$를 빼서 명예는 9ドル-4=5$가 된다.
• 기열 후 맞선임 관계는 새로 계산되며, 이전 맞선임이 더 이상 조건을 만족하지 않을 수 있다.

군대에서는 아래와 같은 쿼리가 주어지니 참고해라.

• 1ドル,円 a,円 b,円 c$: 군번 $a$인 군인의 계급을 $b$로, 명예를 $c$로 변경한다. $(1\leq a\leq N;$ 1ドル\leq b,c\leq 10^9)$
• 2ドル,円 a$: 군번 $a$인 군인을 기열시킨다. 기열 후, 군번 $a$인 군인과 기열 직전 $a$의 맞선임이었던 군인의 계급과 명예를 출력한다. $(1\leq a\leq N)$

훈련병들은 주어진 군대의 계급, 명예, 군번 정보를 바탕으로 쿼리를 처리하도록 한다.

기열 실시! 악!

입력

첫 번째 줄에 군인의 수 $N$이 주어진다. $(2\leq N\leq 100,円 000)$

두 번째 줄에 군번 1ドル$번부터 $N$번까지의 계급값 $R_1,R_2,\ldots ,R_N$이 공백으로 구분되어 주어진다. $(1\leq R_i\leq 10^9)$

세 번째 줄에 군번 1ドル$번부터 $N$번까지의 명예값 $H_1,H_2,\ldots ,H_N$이 공백으로 구분되어 주어진다. $(1\leq H_i\leq 10^9)$

네 번째 줄에 쿼리의 수 $Q$가 주어진다. $(1\leq Q\leq 100,円 000)$

이후 $Q$개의 줄에 걸쳐 다음 두 가지 유형 중 하나의 쿼리가 주어진다.

• 1ドル,円 a,円 b,円 c$: 군번 $a$인 군인의 계급을 $b$로, 명예를 $c$로 변경한다. $(1\leq a\leq N;$ 1ドル\leq b,c\leq 10^9)$
• 2ドル,円 a$: 군번 $a$인 군인을 기열시킨다. 기열 후, 군번 $a$인 군인과 기열 직전 $a$의 맞선임이었던 군인의 기열 후 계급과 명예를 출력한다. $(1\leq a\leq N)$

입력으로 주어지는 수는 모두 정수이다.

2번 쿼리는 1번 이상 주어진다.

출력

2번 쿼리가 주어질 때마다, 다음을 출력한다.

• 군번 $a$인 군인의 기열 후 계급과 명예, 그리고 기열 직전 $a$의 맞선임이었던 군인의 기열 후 계급과 명예를 공백으로 구분하여 한 줄에 출력한다.
• 만약 기열 직전 $a$의 맞선임이 존재하지 않는 경우, 군번 $a$인 군인의 기열 후 계급과 명예, 그리고 -1 -1을 공백으로 구분하여 출력한다.

제한

노트