익스프레스 20/19

플랫랜드의 수도와 인근 도시를 전철로 잇는 철도망은 매우 낡았다. 이를 현대화하기 위해 수도에서 역 하나까지 가는 급행 전철을 운행하기로 결정했다.

플랫랜드 철도망에는 $n$개의 역이 있으며 1번부터 $n$번까지 번호가 붙어 있다. 수도는 1번 역이다. 역 사이에는 단방향 구간이 $m$개 있다. 급행은 각 구간을 번호가 작은 역에서 번호가 큰 역 방향으로만 지날 수 있다. 각 구간을 지나는 데 걸리는 시간이 주어진다.

경로는 구간들의 나열이다. 첫 구간은 수도에서 출발하며, 연속한 두 구간에서는 앞 구간의 도착역이 뒷 구간의 출발역이다. 경로의 소요 시간은 경로에 포함된 모든 구간 시간의 합이다. 역에서 머무는 시간은 무시한다.

교통부는 수도에서 출발하는 경로 후보를 여러 개 검토할 계획이다. 각 후보는 도착역 번호와 예상 소요 시간 $r$로 주어진다. 정확히 $r$에 맞추기 어려울 수 있으므로, 교통부는 매개변수 $p$로 허용 범위를 정한다. 소요 시간이 $x$인 경로는 $r \le x \le \frac{p}{p-1} \cdot r$을 만족하면 예상 시간 $r$에 대해 허용된다.

각 후보에 대해 허용되는 경로가 존재하는지 판단하는 프로그램을 작성하라.

프로그램 한 번의 실행으로 여러 테스트를 처리해야 한다. 첫 줄에는 테스트의 개수 $t$가 주어진다 ($1 \le t \le 1000$). 각 테스트는 다음 형식으로 이어진다.

첫 줄에는 네 정수 $n$, $m$, $q$, $p$가 주어진다. 각각 역의 수, 구간의 수, 후보의 수, 예상 시간에서 허용되는 초과 정도를 정하는 매개변수이다 ($2 \le n \le 500\,000$, $1 \le m \le 500\,000$, $1 \le q \le 500\,000$, $2 \le p \le 20$).

다음 $m$개 줄에는 각각 $v_i$, $u_i$, $d_i$가 주어진다. 출발역, 도착역, 구간을 지나는 시간이다 ($1 \le v_i < u_i \le n$, $1 \le d_i \le 10^{11}$). 모든 역에는 수도에서 그 역으로 끝나는 경로가 최소 하나 존재함이 보장된다.

다음 $q$개 줄에는 각각 $f_i$와 $r_i$가 주어진다. 예상 시간 $r_i$에 대해 역 $f_i$까지 허용되는 경로가 존재하는지 묻는 질의이다 ($2 \le f_i \le n$, $1 \le r_i \le 10^{17}$).

모든 테스트에서 $n$, $m$, $q$의 합은 각각 $500\,000$을 넘지 않는다.

테스트마다 한 줄씩, 총 $t$줄을 출력한다. 각 테스트에 대해 0과 1로 이루어진 길이 $q$의 문자열 $s$를 출력한다. 역 $f_i$까지 소요 시간이 구간 $[r_i, \frac{p}{p-1} \cdot r_i]$에 드는 경로가 존재하면 $s_i$는 $1$이고, 그렇지 않으면 $0$이다.

두 번째 예제에 대한 설명이다.

• 첫 번째 질의에는 소요 시간이 $1 + 120 + 1 = 122$인 경로가 맞다.
• 두 번째 질의에는 소요 시간이 $1 + 1 + 1 = 3$인 경로가 맞다.
• 네 번째 질의에는 소요 시간이 $70 + 1 + 1 = 72$인 경로가 맞다.

세 번째와 다섯 번째 질의에는 맞는 경로가 없다.