Problem Description

There is an unrooted tree with $n$ nodes. Each edge has a positive integer weight representing its length. The distance between two nodes is defined as the length of the shortest path between them in the tree.

You are given, for every node from $2$ to $n-1$, its distance to node $1$ and its distance to node $n$ in the tree. Reconstruct the tree from this information.

Input Format

The first line contains a positive integer $n$, representing the number of nodes.

The second line contains $n-2$ positive integers $d(1,2),d(1,3),...,d(1,n-1)$, representing the distance from each node to node $1$.

The third line contains $n-2$ positive integers $d(n,2),d(n,3),...,d(n,n-1)$, representing the distance from each node to node $n$.

Output Format

If there is no solution, output NIE.

Otherwise, output TAK on the first line. Then output $n-1$ lines, each containing three positive integers $u,v,c$, indicating that there is a tree edge connecting nodes $u$ and $v$ with length $c$.

If there are multiple solutions, output any one of them.

This problem uses a Special Judge.

7
6 6 2 2 1
5 3 5 1 4

TAK
1 5 2
5 7 1
5 2 4
7 3 3
1 4 2
1 6 1

Hint

For $100\%$ of the testdata, $2\le n\le 500000$, $1\le d\le 1000000$, $1\le u,v\le n$, $1\le c\le1000000$.

Translated by ChatGPT 5