파괴왕 뚱뽭

뚱뽭이 살고 있는 세상은 크기가 $N \times M$이고, 크기가 $1 \times 1$인 칸으로 나누어져 있다. 제일 왼쪽 위 칸은 $(1,1)$, 제일 오른쪽 아래 칸은 $(N,M)$이다. 각 칸에는 강도를 가진 기둥이 최대 $1$개 있다.

이 세상에서 한 칸에서 다른 칸으로 이동하려면 다음 규칙을 지켜야 한다.

• 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 이동할 칸에 기둥이 있으면 기둥의 강도만큼 힘을 소모해 기둥을 파괴하고 이동할 수 있다. 남은 힘보다 기둥의 강도가 크면 이동할 수 없다.
• 현재 칸이 순간이동이 가능한 칸이면 한 방향으로 순간이동할 수 있다. 순간이동에는 힘을 소모하지 않는다. 도착 칸에 기둥이 있으면 자동으로 파괴된다. 순간이동은 최대 $T$번 가능하며, 각 칸에서 순간이동으로 갈 수 있는 칸은 최대 $1$개이다.

뚱뽭은 힘 $p$와 목적지 $(x,y)$가 주어질 때, 위 규칙을 지키며 $p$ 이하의 힘으로 $(1,1)$에서 $(x,y)$까지 이동할 수 있는지 궁금해한다. 뚱뽭은 $Q$번의 질문을 한다. 각 질문에서 파괴된 기둥은 다른 질문에 영향을 주지 않는다.

첫 번째 줄에 $N$, $M$, $K$, $T$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N,M,T \le 100;\ 0 \le K \le \min(1\,000, N \times M);\ 1 \le Q \le 100\,000)$

다음 $N$개의 줄에는 각 줄마다 $M$개의 값이 공백으로 구분되어 주어진다. 각 값은 기둥의 강도이며 $0$ 이상 $1\,000$ 이하이다. $0$이면 기둥이 없다는 뜻이다. $(1,1)$은 항상 $0$이다.

다음 $K$개의 줄에는 순간이동이 가능한 칸의 좌표와 도착 칸의 좌표 $x_1, y_1, x_2, y_2$가 공백으로 구분되어 주어진다. 이는 $(x_1,y_1)$에서 $(x_2,y_2)$로 순간이동할 수 있다는 뜻이다. $(1 \le x_1,x_2 \le N;\ 1 \le y_1,y_2 \le M)$

다음 $Q$개의 줄에는 힘 $p$와 목적지 좌표 $x, y$가 공백으로 구분되어 주어진다. $(0 \le p \le 10^8;\ 1 \le x \le N;\ 1 \le y \le M)$

입력으로 주어지는 수는 모두 정수이다.

$Q$개의 줄에, $p$ 이하의 힘으로 $(1,1)$에서 $(x,y)$까지 이동할 수 있으면 $1$을, 없으면 $0$을 출력한다.