29014번 - Железная дорога 스페셜 저지다국어

Через Радиатор-Спрингс проходит крупнейшая железная дорога. Введем на ней систему координат. По железной дороге движутся $n$ поездов. Каждый поезд представляет собой отрезок. Поезд с номером $i$ в начальный момент времени занимает отрезок $[a_i;b_i]$. Поезда не стоят на месте --- $i$-й поезд движется с постоянной скоростью $v_i$. Железная дорога двунаправлена, то есть поезда могут двигаться как в положительном направлении оси, так и в отрицательном. Отрезки, представляющие поезда, в любой момент времени могут пересекаться, вкладываться друг в друга и совпадать.

В точке $x$ находится железнодорожный переезд, к которому в моменты $t_i$ подъезжают тачки. Для каждой тачки требуется вычислить минимальный момент времени, в который она сможет пересечь железнодорожный переезд.

Тачка может пересечь переезд, если он не занят поездом. Переезд считается занятым, если отрезок, представляюший собой некоторый поезд, содержит в себе точку $x$. Причем если поезд подъезжает к перекрестку одновременно тачкой, то переезд считается занятым. Тачки пересекают переезд мгновенно.

В первой строке входного файла три целых числа --- $n$, $m$ и $x$ ($1 \le n, m \le 10^5, |x| \le 10^9$) количество поездов, движущихся по железной дороге, количество тачек, подъезжающих к железнодорожному переезду и точка, в которой находится переезд.

В следующих $n$ строках содержатся по три целых числа $a_i, b_i, v_i$ ($|a_i| \le 10^9$, $|b_i| \le 10^9$, $1 \le v_i \le 10^9, a_i \ne b_i$) --- отрезок, задающий поезд и его скорость движения. Если $a_i < b_i$, то поезд движется в положительном направлении оси, если $a_i > b_i$ --- в отрицательном.

В следующей строке находятся $m$ неотрицательных целых чисел $t_j$ ($0 \le t_j \le 10^9$) --- моменты времени, в которые к переезду подъедут тачки.

В $m$ строках выходного файла выведите $m$ вещественных чисел $b_j$ --- минимальный момент времени, в который $j$-я тачка сможет пересечь железнодорожный переезд. Ответ будет считаться правильным, если относительная или абсолютная погрешность каждого $b_j$ не превосходит $10^{-6}$.