Under construction

Still being built. Things may change

Space Base Construction

Interview

Time limit1sMemory limit128 MB

Summary
For each query rectangle, decide if its center lies on some platform or if at least three of its four corners lie on platforms.
Level

Medium7 of 10

Topics
Geometry, Binary search, Sorting
Solved
No attempts yet

Problem

The Byteotian Space Agency is building a space base on the planet Bajmars. In the first stage, flat rectangular platforms were raised on metal supports above the planet's heavily eroded surface. Every platform sits at the same height, and no two platforms overlap (they may touch along their edges).

In the second stage, various objects are to be placed on these platforms. Each object is a rectangular box described by the rectangle of its base. For every planned object you must decide whether it can stand stably.

An object does not have to rest on the platforms with its entire base. It stands stably on one or more platforms when either of the following holds:

  • its center of gravity lies above the surface of a single platform (a platform's border counts as part of its surface), or
  • at least three of its four base corners rest on platforms.

You may assume the center of gravity lies directly above the point where the diagonals of the base meet, that is, the center of the base rectangle. A corner rests on a platform when it lies inside the platform or on its border, and different corners may rest on different platforms. It does not matter how much of the object hangs over empty space, and it does not matter if the planned objects overlap one another, because these are only plans.

Write a program that reads the platform coordinates and the proposed placements, and for each object reports whether it stands stably.

Input

The first line contains the number of platforms nn, 1≤n≤250001 \le n \le 25000. Each of the next nn lines describes one platform with four integers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2: the coordinates of its lower-left and upper-right corners, where −109≤x1<x2≤109-10^9 \le x_1 < x_2 \le 10^9 and −109≤y1<y2≤109-10^9 \le y_1 < y_2 \le 10^9.

The next line contains the number of planned objects qq, 1≤q≤250001 \le q \le 25000. Each of the next qq lines describes one plan with four integers x1 y1 x2 y2x_1\ y_1\ x_2\ y_2: the lower-left and upper-right corners of that object's base, with the same bounds.

Output

Print exactly qq lines. The jj-th line is TAK if the jj-th object can be placed stably, or NIE otherwise.

Hint

Illustration of platforms and objects

Examples6

  1. Example 1

    Input
    4
5 0 7 3
0 4 3 6
5 7 7 10
1 2 2 3
4
0 5 1 6
2 3 5 5
6 4 8 6
4 7 8 9
    Expected output
    TAK
TAK
NIE
TAK

  2. Example 2

    Input
    1
0 0 10 10
1
2 2 8 8
    Expected output
    TAK

  3. Example 3

    Input
    3
0 0 2 2
4 0 6 2
0 4 2 6
1
0 0 6 6
    Expected output
    TAK

  4. Example 4

    Input
    2
0 0 2 2
4 0 6 2
1
0 0 6 6
    Expected output
    NIE

  5. Example 5

    Input
    1
0 0 4 4
1
2 0 6 4
    Expected output
    TAK

  6. Example 6

    Input
    4
0 0 2 2
2 0 4 2
0 2 2 4
2 2 4 4
1
0 0 4 4
    Expected output
    TAK