문제
최근에 제안된 Visual Python++이라는 프로그래밍 언어에서는, statement block은 왼쪽 위 꼭지점이 r1행 c1열, 오른쪽 아래 꼭지점이 r2행 c2열에 위치한 직사각형 모양으로 나타내어진다.
r1 ≤ r ≤ r2와 c1 ≤ c ≤ c2를 만족하는 모든 (r, c)에 위치한 글자는 block 안에 들어가 있다.
이 글자들 중, r = r1, r = 2, c = c1, c = c2 중 하나라도 만족하는 경우를 경계라고 한다.
Statement block들은 여러 단계로 중첩(직사각형이 다른 직사각형을 포함하는 경우)될 수 있다. 프로그램이 올바르게 구성되기 위해, 모든 두 statement block은 중첩(하나가 다른 하나를 포함)되거나, 떨어져 있어야 (겹치지 않아야)한다. 두 경우 모두, 경계가 겹치면 안 된다.
프로그래머들은 전형적인 프로그램에 많은 직사각형을 그리는 것을 기대하지 않는다 - 이것은 너무 오래 걸리고, 때문에 Visual Python++은 다음 ICPC의 프로그래밍 언어로 사용될 수 없을 것이기 때문이다. 그래서 프로그래머들은 직사각형을 표현하기 위해 오른쪽 위에 ‘p’를, 왼쪽 아래에 ‘y’를 적기만 하면 된다. 파서는 자동으로 가장 적합한 꼭지점들을 매칭시켜 적절한 중첩된 구조를 가진 프로그램을 만들 것이다.
당신은 이 파서를 개발하기 위한 5시간짜리 계약을 따냈다.
입력
첫 번째 줄에 꼭지점 쌍의 개수 n이 주어진다. (1 ≤ n ≤ 105)
두 번째 줄부터 n개의 줄에 왼쪽 위 꼭지점들의 좌표 r, c가 주어진다. (1 ≤ r, c ≤ 109)
n+1 번째 줄부터 n개의 줄에 오른쪽 아래 꼭지점들의 좌표 r, c가 주어진다.
모든 꼭지점의 위치는 다르다.
출력
n개의 줄에 하나의 수를 출력한다. i번째 줄에는 i번째 왼쪽 위 꼭지점과 매칭되는 오른쪽 아래 꼭지점의 번호를 출력한다. 꼭지점 번호는 입력으로 주어진 순서와 동일하다.
출력은 1부터 n까지의 순열이어야 하며, 매칭 결과는 위에서 설명한 중첩 구조를 이뤄야 한다. 만약 만족하는 답이 여러개라면 그 중 하나를 출력한다.
만족하는 답이 없다면, syntax error를 출력한다.
예제 #1
2
4 7
9 8
14 17
19 18
2
1
예제 #2
2
4 7
14 17
9 8
19 18
1
2
예제 #3
2
4 8
9 7
14 18
19 17
syntax error
예제 #4
3
1 1
4 8
8 4
10 6
6 10
10 10
syntax error
로그인해야 코드를 작성할 수 있어요.