N. Shield Navigation
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Enzo is a big fan of the game Lemmings, and his favorite parts of the game are protecting the Lemmings from danger and when they build ramps to travel safely from one place to another.

Since Enzo finds Lemmings a bit outdated, he decided to create a futuristic version of the game. He named his game "Almeidings 3077" and made it in 2D, viewed from above.

In Almeidings 3077, there are several creatures — the Almeidings — that must travel from a starting point $$$(x_i, y_i)$$$ to an endpoint $$$(x_f, y_f)$$$ safely. To parallel the ramp-building mechanics of the original game, Enzo created the concept of Protective Shields. A Protective Shield is a structure built by the Almeidings that allows them to pass safely through dangerous areas.

Enzo defined the following rules for his game:

  • The game is in 2D, and the space can be represented by an $$$N \times M$$$ matrix.
  • A Protective Shield has the shape of a cross and is centered at $$$(x, y)$$$. A Protective Shield centered at $$$(x, y)$$$ protects all the cells in row $$$x$$$ and all the cells in column $$$y$$$.
  • An Almeiding can occupy cell $$$(x, y)$$$ if and only if that cell is protected by a Protective Shield.
  • The Almeidings can move in 4 directions (right, left, up, down):
    • From $$$(x, y)$$$ to $$$(x + 1, y)$$$.
    • From $$$(x, y)$$$ to $$$(x - 1, y)$$$.
    • From $$$(x, y)$$$ to $$$(x, y + 1)$$$.
    • From $$$(x, y)$$$ to $$$(x, y - 1)$$$.

After deciding that the goal of the game is to make the Almeidings conquer the space, Enzo decided to simulate it with your help. He will ask you $$$Q$$$ queries, and each query can be one of two types:

  • Type $$$1$$$: Make an Almeiding build a Protective Shield centered at $$$(x, y)$$$.
  • Type $$$2$$$: If there is an Almeiding at $$$(x_i, y_i)$$$, is it possible for it to reach $$$(x_f, y_f)$$$?

Your task is to answer all type $$$2$$$ queries correctly.

Input

The first line of input contains three integers $$$N$$$, $$$M$$$ $$$(1 \le N \cdot M \le 10^{6})$$$, the dimensions of the matrix representing the game, followed by $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^{5})$$$, the number of queries Enzo will make.

The next $$$Q$$$ lines represent the queries, which can be of two types:

  • $$$1$$$ $$$x$$$ $$$y$$$: Type $$$1$$$, build a Protective Shield centered at $$$(x, y)$$$ $$$(1 \le x \le N, 1 \le y \le M)$$$.
  • $$$2$$$ $$$x_i$$$ $$$y_i$$$ $$$x_f$$$ $$$y_f$$$: Type $$$2$$$, check if an Almeiding can move from $$$(x_i, y_i)$$$ to $$$(x_f, y_f)$$$ $$$(1 \le x_i, x_f \le N)$$$, $$$(1 \le y_i, y_f \le M)$$$.
Output

For each query of type $$$2$$$, print a line containing "SIM" if the Almeiding can reach its goal or "NAO" if it can't.

Examples
Input
3 3 3
1 2 2
2 2 1 2 3
2 1 1 3 3
Output
SIM
NAO
Input
3 3 4
2 1 1 3 3
1 1 1
2 1 1 3 3
2 3 1 1 3
Output
NAO
NAO
SIM