Have you ever wondered what a parking attendant's job looks like? At first glance, it doesn't seem like a difficult task: customers leave cars that need to be parked. Simple? It might seem so, but the reality is more complicated. The main problem for our parking attendant is his boss.

One day, the boss ordered his poor employee to move all the cars in the parking lot according to his whim. The parking attendant, looking at the note his boss brought him and at the note with the current arrangement of cars, wonders if it is even possible. Help him!

We represent the parking lot as a rectangle (on a plane) with height $w$. For convenience, we define a rectangular coordinate system with axes parallel to the sides of the rectangle. The origin of the coordinate system lies in the bottom-left corner of the rectangle. The parking lot is wide enough that it is convenient for us to assume that the right side of the rectangle is infinitely far away.

For simplicity, we also consider cars to be rectangles with sides parallel to the coordinate axes. However, there are larger and smaller cars, so the rectangles corresponding to them may have different sizes. The arrangement of cars in the parking lot is valid if all cars are within the parking lot and no part of the parking lot is occupied by two vehicles at the same time. However, we allow the edges of the rectangles representing the cars to overlap.

The parking attendant has a lot of work experience, so he can move cars in any direction (formally: the parking attendant can always move any car by any vector), as long as the cars do not collide with each other. He cannot, however, rotate them.

Your task is to determine whether it is possible to move the cars from the current position to the position set by the boss without damaging any car.

Input

The first line of the input contains the number of test cases $t$ ($1 \le t \le 20$), which are described sequentially in the rest of the input. The description of each test case begins with a line containing two integers $n, w$ ($1 \le n \le 50\,000$, $1 \le w \le 10^9$), representing the number of cars in the parking lot and the height of the rectangle representing the parking lot.

The next $n$ lines contain the description of the initial arrangement of the cars: the $i$-th of these lines contains four integers $x_1, y_1, x_2, y_2$ ($0 \le x_1, x_2 \le 10^9$, $0 \le y_1, y_2 \le w$), which describe a rectangle with opposite vertices at points $(x_1, y_1)$ and $(x_2, y_2)$, corresponding to the $i$-th car in the parking lot. All rectangles have a positive area.

The next $n$ lines contain the description of the target arrangement of the cars, given in an analogous format. The cars in both descriptions are given in the same order (the $i$-th car from the initial arrangement description corresponds to the $i$-th car from the target arrangement description). The same car may be described in the target arrangement using different vertices than in the initial arrangement. You may assume that both descriptions are valid.

In tests worth 5 points, the additional condition $n \le 1000$ is satisfied.

Output

For each test case, output one line: the $i$-th line should contain the word TAK or NIE, depending on whether it is possible to rearrange the cars according to the boss's requirements in the $i$-th test case.

Examples

Input 1

2
3 3
0 0 2 2
2 1 4 3
4 0 6 1
0 0 2 2
2 1 4 3
0 2 2 3
3 3
0 0 2 2
2 1 4 3
4 0 6 1
2 1 4 3
0 0 2 2
4 0 6 1

Output 1

TAK
NIE

Note

Explanation for the example: The figure shows the first test case from the example. The left part shows the initial arrangement of the cars, and the right part shows the target arrangement. To place car 3 in the correct spot, car 2 must be moved down or to the right. In the second test case, we would have to swap cars 1 and 2, which is not possible.