| r13 ➤ r14 |
| 100 | 라이빗짱 이도혜는 새하얀 AI융합실의 기괴함을 견디지 못하고 바닥에 카펫을 깔기 시작했다. |
| 101 | 코딩 노예로 살아가다 미치광이가 된 이도혜는 강박적인 규칙으로 카펫을 깐다. |
| 102 | |
| 103 | 직사각형 영역(데카르트 좌표계의 제 1사분면)에 직사각형 카펫을 깐다. |
| 104 | 1부터 n까지 번호가 매겨진 총 n개의 카펫이며, |
| 105 | 이 카펫들은 번호 오름차순대로 좌표축에 평행하게 순차적으로 배치된다. |
| 106 | 각 카펫은 이전 카펫을 덮도록 놓인다. |
| 107 | |
| 108 | AI융합실에서 머리에 젤을 바르다 카펫이 깔린 것을 본 임재성은 지면의 특정 지점을 덮고 있는 가장 위쪽 카펫의 번호를 알고 싶어한다.(그 곳에 헤어젤을 흘렸기 때문이다.) |
| 109 | 단, 직사각형 카펫의 경계선과 꼭지점도 카펫으로 간주한다. |
| 110 | |
| 111 | 카펫이 깔린 예시다. |
| 112 | [[file:이도혜의카펫.png]] |
| 113 | 실선: 카펫1번, 점선: 카펫2번, 이중선: 카펫3번이다. 좌표(2,2)는 카펫 3이다. 좌표(4,5)에는 아무것도 없다. |
| 114 | |
| 115 | |
| 116 | *입력 설명 |
| 117 | 각 입력 데이터 셋은 n+2개의 행으로 구성된다. |
| 118 | 첫 번째 줄에는 카펫의 총 개수 n이 입력된다. |
| 119 | i+1번째 줄에는 i번째 카펫에 대한 정보가 들어있다. 이 정보는 공백으로 구분된 네 개의 양의 정수 a, b, g, k로 구성된다. |
| 120 | 이 정수들은 각각 카펫의 왼쪽 아래 모서리 좌표(a,b)와 x축 및 y축을 따라 측정한 카펫의 길이를 나타낸다. |
| 121 | n+2번째 줄에는 지면 위 점의 좌표를 나타내는 두 개의 양의 정수 x와 y가 적혀있다. |
| 122 | 0<=n<=10,000, 0<=a,b,g,k<=100,000 이다 |
| 123 | |
| 124 | *출력 설명 |
| 125 | 각 출력은 한 줄로 구성되며, 해당 위치에 카펫이 있으면 가장 위의 카펫 번호를 출력한다. 해당 위치에 카펫이 없으면 -1을 출력한다. |
| 126 | |
| 127 | *입력 예시 |
| 128 | 3 |
| 129 | 1 0 2 3 |
| 130 | 0 2 3 3 |
| 131 | 2 1 3 3 |
| 132 | 2 2 |
| 133 | |
| 134 | *출력 예시 |
| 135 | 3 |
