시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB6911917.308%

문제

Система, связывающая столицу Флатландии с соседними городами с помощью электричек, сильно устарела. Для её модернизации было принято решение пустить из столицы до одной из станций электричку-экспресс.

Всего в железнодорожной сети Флатландии $n$ станций, пронумерованных целыми числами от $1$ до $n$, сама столица имеет номер $1$. Всего существует $m$ односторонних перегонов между станциями. По каждому из них экспресс может проехать от станции с меньшим номером до станции с бóльшим номером. Для каждого перегона известно время, за которое экспресс проезжает этот перегон.

Маршрутом будем называть некоторую последовательность перегонов, такую, что первый перегон начинается в столице, и для любых двух последовательных перегонов начало второго совпадает с концом первого. Время проезда по маршруту равно суммарному времени прохождения всех этих перегонов, временем стоянки на станциях следует пренебречь.

Министерство транспорта Флатландии планирует рассмотреть несколько вариантов маршрута экспресса от столицы. Каждый вариант характеризуется номером станции, до которой следует пустить экспресс, и ориентировочным временем проезда по маршруту. При этом, в министерстве понимают, что точно выполнить требование о времени проезда может оказаться невозможно. Поэтому они используют для оценки допустимости маршрута величину $p$: маршрут с временем проезда $x$ является допустимым для ориентировочного времени $r$, если $r \le x \le \frac{p}{p-1} \cdot 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$ строках находятся по три целых числа, описывающих $i$-й перегон: $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$ --- требование проверить существование допустимого маршрута до станции $f_i$ с ориентировочным временем проезда $r_i$ ($2 \le f_i \le n$, $1 \le r_i \le 10^{17}$).

Гарантируется, что каждая из сумм значений $n$, значений $m$ и значений $q$ по всем тестам одних входных данных не превосходит $500\,000$.

출력

Выведите $t$ строк, по одной для каждого заданного во входных данных теста.

В качестве ответа на тест выведите строку $s$ длины $q$, состоящую из символов $0$ и $1$. Символ $s_i$ должен быть равен $1$, если для $i$-го варианта существует допустимый маршрут, то есть маршрут до станции $f_i$, время проезда по которому лежит в отрезке $[r_i, \frac{p}{p - 1} \cdot r_i]$, и $0$ --- в противном случае.

서브태스크

번호배점제한
115

$n \le 10$, $m \le 10$, $q \le 10$

224

$\sum n \le 5000$, $\sum m \le 5000$, $\sum q \le 5000$

$r_i \le 5\,000$

317

$m = 2n - 2$, $q \le 10$

$p = 2$, каждый перегон соединяет станции с номерами $i$ и $i + 1$, причем из вершины $i$ в вершину $i + 1$ проведено ровно два перегона для всех $1 \le i \le n - 1$

411

$m = 2n - 2$

Каждый перегон соединяет станции с номерами $i$ и $i + 1$, причем из вершины $i$ в вершину $i + 1$ проведено ровно два перегона для всех $1 \le i \le n - 1$

511

$\sum n \le 1000$, $\sum m \le 2000$

Все $r_i$ равны

611

Все $r_i$ равны

711

예제 입력 1

2
3 3 5 20
1 2 20
2 3 1
1 3 10
2 19
2 20
3 20
3 21
3 9
7 10 5 5
1 2 15
1 3 10
2 4 21
3 4 30
2 5 14
3 5 31
4 6 3
5 6 14
1 7 39
5 7 13
7 42
7 43
7 44
5 39
6 44

예제 출력 1

11110
10111

예제 입력 2

1
4 6 5 2
1 2 1
2 3 1
3 4 1
1 2 70
2 3 120
3 4 4
4 90
4 2
4 10
4 37
2 34

예제 출력 2

11010

힌트

Во втором примере:

  • В первом запросе подойдёт маршрут с временем $1 + 120 + 1 = 122$.
  • Во втором запросе подойдёт маршрут с временем $1 + 1 + 1 = 3$.
  • В четвёртом запросе подойдёт маршрут с временем $70 + 1 + 1 = 72$.

Для третьего и пятого запроса нет ни одного подходящего маршрута.

채점 및 기타 정보

  • 예제는 채점하지 않는다.