Destroyer King Ttungppup

The world where Ttungppup lives is an $N \times M$ grid of $1 \times 1$ cells. The top left cell is $(1,1)$ and the bottom right cell is $(N,M)$. Each cell holds at most one pillar, and each pillar has a strength.

To move from one cell to another in this world, you must follow these rules.

• From the current cell, you can move to an adjacent cell up, down, left, or right. If the target cell has a pillar, you spend energy equal to its strength to destroy it and move there. You cannot move if the pillar's strength is greater than your remaining energy.
• If the current cell allows teleportation, you can teleport in one direction. Teleporting costs no energy. If the destination cell has a pillar, the pillar is destroyed automatically. You can teleport at most $T$ times, and each cell has at most one teleport destination.

Given an energy $p$ and a destination $(x,y)$, Ttungppup wants to know whether he can move from $(1,1)$ to $(x,y)$ using at most $p$ energy while following these rules. He asks $Q$ questions. Pillars destroyed in one question do not affect the others.

The first line contains $N$, $M$, $K$, $T$, and $Q$, separated by spaces. $(1 \le N,M,T \le 100;\ 0 \le K \le \min(1\,000, N \times M);\ 1 \le Q \le 100\,000)$

Each of the next $N$ lines contains $M$ values separated by spaces. Each value is the strength of the pillar in that cell, between $0$ and $1\,000$. A value of $0$ means the cell has no pillar. $(1,1)$ is always $0$.

Each of the next $K$ lines contains four integers $x_1, y_1, x_2, y_2$ separated by spaces. This means you can teleport from $(x_1,y_1)$ to $(x_2,y_2)$. $(1 \le x_1,x_2 \le N;\ 1 \le y_1,y_2 \le M)$

Each of the next $Q$ lines contains an energy $p$ and a destination $x, y$ separated by spaces. $(0 \le p \le 10^8;\ 1 \le x \le N;\ 1 \le y \le M)$

All input values are integers.

For each question, print $1$ on a separate line if you can reach $(x,y)$ from $(1,1)$ using at most $p$ energy. Otherwise, print $0$.