City Tour

Time limit1sMemory limit128 MB

Summary

Given a connected 4-regular multigraph with an object on each edge, decide whether some closed Eulerian tour starting at an edge midpoint never lets accumulated interest drop below zero.

Level: Hard8 of 10
Topics: Graph, Greedy, Implementation, Math
Solved: No attempts yet

Problem

The tourist agency of Byteland is about to launch sightseeing tours along the streets of Bytenburg aboard an open-top bus. Every tour starts and finishes at the agency's centre, and you must decide in the middle of which street that centre will be built.

So that tourists never suspect they missed something interesting, the route of a tour must cover every street of the city. Streets need not be straight and may run through tunnels or viaducts. There are no one-way streets. Each street connects two crossroads, and four streets meet at every crossroad (so every crossroad has degree four). Two crossroads may be joined by more than one street. You may not turn around in the middle of a street, but you may turn around at a crossroad. From any crossroad you can reach any other crossroad through the streets (the graph is connected).

Exactly in the middle of each street there is one object worth seeing (a view, a sculpture, a monument, and so on). The degree of attraction of an object is a non-negative integer. The centre is built next to one such object, that is, in the middle of some street.

During a tour the interest of the tourists changes as follows:

driving one byte-mile lowers the interest by $1$ ;
seeing an object for the first time raises the interest by that object's degree of attraction;
at the start of the tour the interest equals the degree of attraction of the object next to the centre.

A route is called attractive if the interest never drops below $0$ at any moment of the tour.

Given the city, decide whether an attractive tour route exists.

Input

The first line contains the number of crossroads $n$ ( $1 < n \le 10\,000$ ). Crossroads are numbered from $1$ to $n$ , and streets from $1$ to $2n$ .

Each of the next $2n$ lines describes one street. The $(i+1)$ -th line describes street $i$ with four integers $a$ , $b$ , $l$ , $s$ separated by single spaces. $a$ and $b$ are the crossroads joined by the street ( $1 \le a, b \le n$ , $a \ne b$ ). $l$ is even and is the length of the street in byte-miles ( $2 \le l \le 1000$ ). $s$ is the degree of attraction of the object in the middle of the street ( $0 \le s \le 1000$ ).

Output

Print TAK if an attractive tour route exists, and NIE otherwise. (TAK and NIE mean "yes" and "no" in Polish.)

Examples3

Example 1

Input

Expected output

TAK

Example 2
Input
```
2
1 2 2 2
1 2 2 2
1 2 2 2
1 2 2 2
```
Expected output
```
TAK
```
Example 3
Input
```
2
1 2 2 0
1 2 2 0
1 2 2 0
1 2 2 0
```
Expected output
```
NIE
```