도시 관광

바이트랜드(Byteland)의 도시 바이텐부르크(Bytenburg)에서 오픈카 버스를 타고 거리를 도는 관광 상품을 준비하고 있다. 모든 관광은 회사 본부에서 출발해 본부에서 끝나며, 이 본부를 어느 거리 한가운데에 세울지 정해야 한다.

관광객이 무언가를 놓쳤다고 느끼지 않도록, 관광 경로는 도시의 모든 거리를 빠짐없이 지나야 한다. 거리는 곧게 뻗어 있지 않을 수 있고 터널이나 고가로 이어질 수도 있다. 일방통행 거리는 없다. 각 거리는 두 교차로를 잇고, 모든 교차로에서는 네 방향으로 거리가 뻗어 있다(즉 모든 교차로의 차수는 4이다). 두 교차로를 잇는 거리가 둘 이상일 수도 있다. 거리 중간에서는 방향을 되돌릴 수 없지만 교차로에서는 되돌 수 있다. 또한 거리망을 통해 어느 교차로에서든 다른 어느 교차로로도 갈 수 있다(그래프는 연결되어 있다).

각 거리의 정확히 한가운데에는 관광객이 볼 만한 대상(전망, 조각상, 기념물 등)이 하나씩 있다. 대상의 매력도는 음이 아닌 정수로 나타낸다. 본부는 이런 대상 하나의 옆, 즉 어떤 거리의 한가운데에 세운다.

관광이 진행되는 동안 관광객의 흥미는 다음과 같이 변한다.

• 버스로 $1$ byte-mile를 이동할 때마다 흥미가 $1$ 줄어든다.
• 어떤 대상을 처음 볼 때, 그 대상의 매력도만큼 흥미가 늘어난다.
• 관광 시작 시점의 흥미는 본부가 있는 거리의 대상의 매력도와 같다.

관광 경로가 진행되는 동안 흥미가 한 번도 $0$ 아래로 떨어지지 않으면 그 경로를 매력적(attractive)이라고 한다.

주어진 도시에서 매력적인 관광 경로가 존재하는지 판정하는 프로그램을 작성하라.

첫째 줄에 교차로의 수 $n$이 주어진다 ($1 < n \le 10\,000$). 교차로는 $1$부터 $n$까지 번호가 매겨져 있고, 거리는 $1$부터 $2n$까지 번호가 매겨져 있다.

이어지는 $2n$개의 줄에 거리 정보가 하나씩 주어진다. $i+1$번째 줄에는 $i$번째 거리를 나타내는 네 정수 $a$, $b$, $l$, $s$가 공백으로 구분되어 주어진다. $a$와 $b$는 이 거리가 잇는 두 교차로의 번호로 $1 \le a, b \le n$이고 $a \ne b$이다. $l$은 짝수이며 이 거리의 길이(byte-mile)로 $2 \le l \le 1000$이다. $s$는 이 거리 한가운데 있는 대상의 매력도로 $0 \le s \le 1000$이다.

매력적인 관광 경로가 존재하면 첫째 줄에 TAK을, 존재하지 않으면 NIE를 출력한다. (TAK과 NIE는 각각 폴란드어로 "예"와 "아니오"를 뜻한다.)