기열과 쿼리
시간 제한1초메모리 제한1024 MB
N명의 군인이 계급과 명예를 가지며, 갱신 쿼리로 한 군인의 값을 바꾸고 기열 쿼리마다 상황에 따라 다시 정해지는 맞선임에게 명예 절반을 바치고 두 사람의 값을 출력한다.
문제
본 병장이 군대에서 지켜야 할 중요한 문화, 기열에 대해 설명하겠다. 군대는 명의 군인으로 이루어져 있으며, 각 군인은 계급, 명예, 그리고 고유한 군번을 가진다. 군번은 부터 까지 겹치지 않게 부여되며, 계급과 명예는 값이 클수록 높다. 군대에서는 계급과 명예를 바탕으로 맞선임 관계가 정의되며, 모든 군인은 기열 문화를 따라야 한다.
각 군인에게 1명 또는 0명 존재하는 맞선임은 다음과 같이 결정된다.
- 계급이 자신과 동일한 군인 중에서, 명예가 자신보다 높으면서 가장 낮은 명예를 가진 군인을 맞선임으로 삼는다.
- 만약 위 조건에 해당하는 군인이 없다면, 계급이 자신보다 높으면서 현재 존재하는 가장 낮은 계급을 가진 군인 중 가장 낮은 명예를 가진 군인을 맞선임으로 삼는다.
- 맞선임 조건에 부합하는 군인이 여러 명일 경우, 그중 군번이 가장 큰 군인이 맞선임이 된다.
- 계급과 명예가 모두 자신과 동일한 군인은 맞선임이 될 수 없다. 이는 동기 관계로 간주한다.
- 맞선임이 없는 경우, 맞선임은 존재하지 않는다.
기열 문화를 알려주겠다. 기열은 군인들에게 부과되는 의식으로, 다음과 같은 규칙을 따른다.
- 군인은 자신의 명예 값의 절반을 맞선임에게 바쳐야 한다. 이 과정에서 명예는 항상 정수로 유지되며 소수점은 버림 처리된다.
- 예를 들어, 명예가 인 군인 안지민과 그의 맞선임 장성혁(명예 , 계급 로 안지민과 동일)이 있다고 하자. 안지민이 기열을 수행하면 의 명예를 장성혁에게 바친다. 이에 따라 안지민의 명예는 가 되고, 장성혁의 명예는 이 된다.
- 맞선임이 없는 경우, 군인은 자신의 명예 값에서 절반을 버림 처리한 값을 빼며, 군대의 자비로운 정책에 따라 소수점은 버림 처리된다. 예를 들어, 명예가 인 군인이 맞선임 없이 기열을 수행하면 를 빼서 명예는 가 된다.
- 기열 후 맞선임 관계는 새로 계산되며, 이전 맞선임이 더 이상 조건을 만족하지 않을 수 있다.
군대에서는 아래와 같은 쿼리가 주어지니 참고해라.
- : 군번 인 군인의 계급을 로, 명예를 로 변경한다.
- : 군번 인 군인을 기열시킨다. 기열 후, 군번 인 군인과 기열 직전 의 맞선임이었던 군인의 계급과 명예를 출력한다.
훈련병들은 주어진 군대의 계급, 명예, 군번 정보를 바탕으로 쿼리를 처리하도록 한다.
기열 실시! 악!
입력
첫 번째 줄에 군인의 수 이 주어진다.
두 번째 줄에 군번 번부터 번까지의 계급값 이 공백으로 구분되어 주어진다.
세 번째 줄에 군번 번부터 번까지의 명예값 이 공백으로 구분되어 주어진다.
네 번째 줄에 쿼리의 수 가 주어진다.
이후 개의 줄에 걸쳐 다음 두 가지 유형 중 하나의 쿼리가 주어진다.
- : 군번 인 군인의 계급을 로, 명예를 로 변경한다.
- : 군번 인 군인을 기열시킨다. 기열 후, 군번 인 군인과 기열 직전 의 맞선임이었던 군인의 기열 후 계급과 명예를 출력한다.
입력으로 주어지는 수는 모두 정수이다.
2번 쿼리는 1번 이상 주어진다.
출력
2번 쿼리가 주어질 때마다, 다음을 출력한다.
- 군번 인 군인의 기열 후 계급과 명예, 그리고 기열 직전 의 맞선임이었던 군인의 기열 후 계급과 명예를 공백으로 구분하여 한 줄에 출력한다.
- 만약 기열 직전 의 맞선임이 존재하지 않는 경우, 군번 인 군인의 기열 후 계급과 명예, 그리고
-1 -1을 공백으로 구분하여 출력한다.