지하철 계획

Bajtazar는 바이트고르드로 여행을 떠나 도시에 머무는 동안 내내 지하철을 타기로 했다. 그는 기차역에서 내렸는데, 그곳에 지하철역이 하나 있다. 그는 자동판매기에서 표를 사려고 했다. 요금표에 따르면 "Railway station" 역에서 "Airport" 역까지 가는 구간은 무료이고, 그 밖의 모든 구간의 표 가격은 출발역과 도착역 사이의 거리와 같다. 바이트고르드를 찾는 승객을 위해 자동판매기 옆에는 "Railway station"에서 다른 모든 역까지의 표 가격 목록과 "Airport"에서 다른 모든 역까지의 표 가격 목록이 붙어 있다. Bajtazar는 지하철에 역이 $n$개 있고, 길이가 양수인 터널 $n - 1$개로 연결되어 있다는 것도 알게 되었다. 이 터널들은 최소한의 개수이지만, 어느 역에서든 다른 어느 역으로 갈 수 있을 만큼 충분하다. 그는 이 정보를 바탕으로 역 사이의 연결을 구하거나, 가지고 있는 정보가 잘못되었다고 판단하고 싶어 한다.

첫 줄에는 바이트고르드 지하철의 역 수를 나타내는 양의 정수 $n$이 주어진다. 역은 1부터 $n$까지 번호가 매겨져 있으며, "Railway station"은 1번 역, "Airport"는 $n$번 역이다. 둘째 줄에는 범위 $[1, 1\,000\,000]$의 정수 $d_2, d_3, \ldots, d_{n-1}$이 공백으로 구분되어 주어진다. $i$번째 수는 "Railway station"에서 $i$번 역까지의 표 가격이며, 이 가격은 그 경로의 길이와 같다. 셋째 줄에는 같은 형식으로 $l_2, l_3, \ldots, l_{n-1}$이 주어지며, 이는 "Airport"에서 각 역까지의 표 가격이다.

Bajtazar가 얻은 정보와 맞는 역 간 연결 계획이 없으면 NIE를 한 줄에 출력한다. 그렇지 않으면 첫 줄에 TAK를 출력하고, 이어서 $n - 1$개의 줄에 연결을 출력한다. 각 줄에는 공백으로 구분된 정수 $a$, $b$, $c$가 있으며, 이는 $a$번 역과 $b$번 역이 길이 $c$인 터널로 연결되어 있다는 뜻이다. 올바른 답이 여러 개이면 그중 아무거나 출력하면 된다.

$n \le 500\,000$

아래 그림은 Bajtazar가 얻은 정보와 맞는 연결망을 보여 주며, 터널의 길이도 함께 표시되어 있다.