정사각형일까, 직사각형일까?

나는 정사각형일 수도, 직사각형일 수도 있다. 나는 정사각형일까, 직사각형일까?

$N \times N$개의 격자 칸을 생각하자. 어떤 정사각형 또는 직사각형이 격자 칸 일부를 덮고 있고, 각 격자 칸은 도형의 내부에 완전히 들어가거나 완전히 바깥에 있다. 즉 도형의 경계는 격자선을 따른다. 두 가지 예가 아래에 있다.

그림 1: 나는 정사각형이다.	그림 2: 나는 직사각형이다.

도형은 격자 전체 넓이의 최소 4%를 덮는다. 여러분은 도형이 정사각형인지 직사각형인지 판별해야 한다. 이를 위해 최대 $Q$번의 질의를 할 수 있고, 질의마다 특정 격자 칸이 도형 내부에 있는지 알아낼 수 있다. 격자 칸은 좌표 $(x, y)$로 나타내며 $1 \le x, y \le N$이다.

• $N = 100$
• $1 \le T \le 1000$