시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 267 28 23 19.328%

문제

선영이는 핀볼 중독자이다. 선영이는 항상 자신이 원하는 위치에 공을 맞출 수 있다. 하지만, 공이 범퍼에 많이 튕기기 때문에, 어디로 떨어질지는 정확하게 예측하지 못한다.

결국 선영이는 핀볼 테이블을 선분으로, 공을 높이가 무한대인 곳에서 떨어지는 점으로 모델링했다. 공은 선분을 만나기 전까지 수직으로 떨어지며, 선분을 만난 이후에는 선분의 아랫방향으로 공이 흘러간다.

선분의 끝점도 선분에 포함된다. 선분은 서로 교차하지 않으며, 선분의 끝점 또한 교차하지 않는다. 선분은 수직선이나 수평선이 아니다. 또, 입력으로 주어지는 순서에는 아무 의미가 없다.

입력

첫째 줄에 선분의 개수 N이 주어진다. (0 ≤ N ≤ 100,000) 다음 N개 줄에는 선분의 양 끝점 좌표 x1 y1 x2 y2가 주어진다. (-1,000,000 ≤ xi, yi ≤ 1,000,000) 마지막 줄에는 공의 맨 처음 x좌표 x0이 주어진다. (-1,000,000 ≤ x0 ≤ 1,000,000) 모든 좌표는 정수이다.

출력

첫째 줄에 공의 최종 위치 x좌표를 출력한다.

예제 입력 1

2
-1 1 1 -1
1 -2 2 -3
0

예제 출력 1

2

예제 입력 2

3
-1 1 1 -1
1 -2 0 -3
1 -3 2 -4
0

예제 출력 2

0

힌트

W3sicHJvYmxlbV9pZCI6IjkyNDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NDBcdWJjZmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ1NDBcdWJjZmMgXHVjOTExXHViM2M1XHVjNzkwXHVjNzc0XHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVkNTZkXHVjMGMxIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNWQwIFx1YWNmNVx1Yzc0NCBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFjZjVcdWM3NzQgXHViYzk0XHVkMzdjXHVjNWQwIFx1YjljZVx1Yzc3NCBcdWQyOTVcdWFlMzBcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM1YjRcdWI1MTRcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWM4XHVjOWMwXHViMjk0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWM2MDhcdWNlMjFcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjYjBcdWFkNmQgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1ZDU0MFx1YmNmYyBcdWQxNGNcdWM3NzRcdWJlMTRcdWM3NDQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjLCBcdWFjZjVcdWM3NDQgXHViMTkyXHVjNzc0XHVhYzAwIFx1YmIzNFx1ZDU1Y1x1YjMwMFx1Yzc3OCBcdWFjZjNcdWM1ZDBcdWMxMWMgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWJhYThcdWIzNzhcdWI5YzFcdWQ1ODhcdWIyZTQuIFx1YWNmNVx1Yzc0MCBcdWMxMjBcdWJkODRcdWM3NDQgXHViOWNjXHViMDk4XHVhZTMwIFx1YzgwNFx1YWU0Y1x1YzljMCBcdWMyMThcdWM5YzFcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWMxMjBcdWJkODRcdWM3NDQgXHViOWNjXHViMDljIFx1Yzc3NFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NTggXHVjNTQ0XHViN2FiXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YWNmNVx1Yzc3NCBcdWQ3NThcdWI3ZWNcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWIwNWRcdWM4MTBcdWIzYzQgXHVjMTIwXHViZDg0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxY1x1YjJlNC4gXHVjMTIwXHViZDg0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWMxMjBcdWJkODRcdWM3NTggXHViMDVkXHVjODEwIFx1YjYxMFx1ZDU1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWMxMjBcdWJkODRcdWM3NDAgXHVjMjE4XHVjOWMxXHVjMTIwXHVjNzc0XHViMDk4IFx1YzIxOFx1ZDNjOVx1YzEyMFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YjYxMCwgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0IFx1Yzc1OFx1YmJmOFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NTggXHVjNTkxIFx1YjA1ZFx1YzgxMCBcdWM4OGNcdWQ0NWMgeDxzdWI+MTxcL3N1Yj4geTxzdWI+MTxcL3N1Yj4geDxzdWI+MjxcL3N1Yj4geTxzdWI+MjxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEsMDAwLDAwMCAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCkgXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWM3NTggXHViOWU4IFx1Y2M5OFx1Yzc0YyB4XHVjODhjXHVkNDVjIHg8c3ViPjA8XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xLDAwMCwwMDAgJmxlOyB4PHN1Yj4wPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCkgXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjZjVcdWM3NTggXHVjZDVjXHVjODg1IFx1YzcwNFx1Y2U1OCB4XHVjODhjXHVkNDVjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waW5iYWxsLnBuZ1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTI0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpbmJhbGwiLCJkZXNjcmlwdGlvbiI6IjxwPk1hcmlhIGlzIHF1aXRlIGFkZGljdGVkIHRvIHBpbmJhbGwuIFNoZSBjYW4gc2hvb3QgdGhlIGJhbGwgdG8gYW55IHBvc2l0aW9uIGF0IHRoZSB0b3Agb2YgdGhlIGJvYXJkLCBidXQgc2hlIGNhbm5vdCBwcmVkaWN0IHdoZXJlIHRoZSBiYWxsIHdpbGwgZW5kIHdoZW4gaXQgZmFsbHMgZG93biwgYmVjYXVzZSBpdCBoaXRzIG1hbnkgYnVtcGVycyBvbiBpdHMgd2F5IGRvd24uPFwvcD5cclxuXHJcbjxwPlNoZSBkZWNpZGVkIHRvIG1vZGVsIHRoZSBwaW5iYWxsIHRhYmxlIGFzIGxpbmUgc2VnbWVudHMgYW5kIGFzc3VtZSBlIHRoYXQgdGhlIGJhbGwgaXMgYSBwb2ludCB0aGF0IGZhbGxzIGZyb20gaW5cdWZiMDFuaXRlIGhlaWdodC4gVGhlIGJhbGwgZmFsbHMgc3RyYWlnaHQgdmVydGljYWxseSB1bmxlc3MgdGhlcmUgaXMgYSBzZWdtZW50IGltbWVkaWF0ZWx5IGJlbG93IGl0LCBpbiB3aGljaCBjYXNlIGl0IGZvbGxvd3MgdGhlIGRpcmVjdGlvbiBvZiB0aGUgc2VnbWVudCBkb3dud2FyZHMgdW50aWwgaXRzIGVuZC48XC9wPlxyXG5cclxuPHA+QXMgeW91IHdvdWxkIGV4cGVjdCB0aGUgc2VnbWVudHMgYXJlIGNsb3NlZCwgdGhhdCBpcyBhbiBlbmRwb2ludCBpcyBwYXJ0IG9mIGl0cyBzZWdtZW50LiBQYWlycyBvZiBzZWdtZW50cyBkbyBub3QgaW50ZXJzZWN0LCBub3QgZXZlbiBhdCBlbmRwb2ludHMsIGFuZCBub25lIGlzIHZlcnRpY2FsIG9yIGhvcml6b250YWwuIFNlZ21lbnRzIGFyZSBub3QgZ2l2ZW4gaW4gYW55IHNwZWNpXHVmYjAxYyBvcmRlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMCAmbGU7IE4gJmxlOyAxMDAsMDAwKSwgdGhlIG51bWJlciBvZiBzZWdtZW50cy4gVGhlbiBOIGxpbmVzIGZvbGxvdywgZWFjaCB3aXRoIGZvdXIgaW50ZWdlcnMgeDxzdWI+MTxcL3N1Yj4geTxzdWI+MTxcL3N1Yj4geDxzdWI+MjxcL3N1Yj4geTxzdWI+MjxcL3N1Yj4sIHRoZSBjb29yZGluYXRlcyBvZiBhIHNlZ21lbnQgKC0xLDAwMCwwMDAgJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDApLiBUaGUgbGFzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgeDxzdWI+MDxcL3N1Yj4gKC0xLDAwMCwwMDAgJmxlOyB4PHN1Yj4wPFwvc3ViPiAmbGU7IDEsMDAwLDAwMCksIHRoZSBpbml0aWFsIHgtY29vcmRpbmF0ZSBvZiB0aGUgYmFsbC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlciB4PHN1Yj5UPFwvc3ViPiwgdGhlIFx1ZmIwMW5hbCB4LWNvb3JkaW5hdGUgb2YgdGhlIGJhbGwuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==