32646번 - 파괴왕 뚱뽭

문제

뚱뽭이 살고 있는 세상은 크기가 $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ドル$을 출력한다.

제한

힌트