Recently, the Wah Yan Kingdom recruited a new programmer, GL, to join their WYKOJ game development team. Instead of spending his time binge-watching anime or making mobile games, GL decided to create the greatest game in the world and eventually dominate the gaming world. Inspired by a famous novel, he developed a new game called "The Maze Runner."

In this game, the maze is represented as an $N \times M$ rectangular grid. The rows of the grid are numbered from $1$ to $N$ (from top to bottom), and the columns are numbered from $1$ to $M$ (from left to right). The cell located in the $r$-th row and $c$-th column is denoted as $(r, c)$. Initially, no cells are blocked, and the player starts at cell $(X, Y)$.

The player can move to any adjacent cell that shares an edge, as long as it’s not blocked. Specifically, if the player is at $(r, c)$, they can move to:

• $(r-1, c)$ if $r > 1$ and the cell $(r-1, c)$ is not blocked.
• $(r+1, c)$ if $r < N$ and the cell $(r+1, c)$ is not blocked.
• $(r, c-1)$ if $c > 1$ and the cell $(r, c-1)$ is not blocked.
• $(r, c+1)$ if $c < M$ and the cell $(r, c+1)$ is not blocked.

Since "The Maze Runner" is an open-world game, the player should have access to resources early in the game. GL wants to know if it's possible to move from the starting cell $(X, Y)$ to some specific cells, so he can place resources in those locations while making modifications to the maze. Knowing you're good at games, GL has asked you to help test it. GL will issue $Q$ queries of the following types:

1. Determine if the player can move from $(X, Y)$ to $(R_i, C_i)$.
2. Block the cell located at $(R_i, C_i)$.

It is guaranteed that $(R_i, C_i)$ is not blocked before any query, and the starting cell $(X, Y)$ will never be blocked.

Input

The first line contains five integers: $N$, $M$, $Q$, $X$, and $Y$.
The following $Q$ lines each contain three integers representing a query.
Each query contains three integers: $T_i$, $R_i$ and $C_i$. $T_i$ represents the type of the $i$-th query (1 or 2).

Output

For each query of type 1, output 1 if the player can move from $(X, Y)$ to $(R_i, C_i)$, and 0 otherwise.

Constraints

For all cases, $1 \le N, M, Q \le 10^5$, $1 \le T_i \le 2$, $1 \le R_i, X \le N$, and $1 \le C_i, Y \le M$. It is guaranteed that at least one type 1 query appears.
Subtask 1 (10%): $N=1$ or $M=1$.
Subtask 2 (15%): $1 \le N, M, Q \le 100$.
Subtask 3 (25%): $1 \le N, M \le 1000$.
Subtask 4 (30%): No type 2 queries are issued after a type 1 query.
Subtask 5 (20%): No additional constraints.