Поезд Одинцово-Мурино

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

По этой железной дороге перемещаются n поездов, перевозящих счастливых пассажиров между двумя столицами. Поезда пронумерованы числами от 1 до n. Для удобства представим железную дорогу как прямую, на которой введена система координат. Каждый день в 4:00 по Одинцовскому времени все поезда одновременно начинают свое движение, причем i-й поезд имеет постоянную скорость vi километров в час. Перед началом движения i-й поезд занимает собой отрезок железной дороги [ai,bi]. Разумеется, по железной дороге поезда могут перемещаться в обоих направлениях. Также благодаря использованию новейших изобретений в области квантовой механики, если в какой-то момент времени отрезки, соответствующие некоторым двум поездам, пересеклись на прямой, то столкновения не происходит и поезда продолжают двигаться как и ранее по своим траекториям, так как каждый поезд находится в своем пространственно-временном континууме.

К сожалению, пешеходный переход через железную дорогу построили только в одном месте— в точке с координатой x. Известно, что спустя t1,t2,…,tm часов после начала движения поездов в данной точке к железной дороге будут подходить люди, желающих перейти дорогу. Каждый человек может мгновенно перейти дорогу, потратив на это 0 единиц времени. Однако, люди не могут перейти железную дорогу, если в данный момент существует хотя бы один поезд, отрезок которого содержит в себе точку x. От вас требуется для каждого человека вычислить минимальный момент времени, в который он сможет перейти железную дорогу.

Формат входных данных
Первая строка содержит три целых числа n, m и x (1⩽n,m⩽105,−109⩽x⩽109) — количество поездов, количество людей, а также координату точки, в которой находится пешеходный переход.

Каждая из следующих n строк содержит три целых числа ai, bi и vi (−109⩽ai,bi⩽109, 1⩽vi⩽109,ai≠bi) — отрезок, соответствующий положению поезда в момент начала движения, а также скорость поезда. Если ai<bi, то поезд движется в положительном направлении оси, а если ai>bi — то в отрицательном направлении.

Последняя строка содержит m целых чисел t1,t2,…,tm (0⩽tj⩽109) — моменты времени, в которые к пешеходному переходу подходят люди.

Все расстояния измеряются в километрах, а моменты времени — в часах после начала движения поездов.

Формат выходных данных
Выведите m строк, в каждой из которых выведите одно вещественное число ci — минимальное время в часах после начала движения поездов, в которое i-й человек сможет перейти железную дорогу.

Ответ будет считаться правильным, если относительная или абсолютная погрешность каждого ci не превосходит 10−6.

Пояснение к примеру
Рассмотрим пример из условия.

В момент времени 0 поезда будут соответствовать отрезкам [−5,−2], [5,12] и [−8,−7], поэтому перейти дорогу в точке −1 возможно.

В момент времени 133 поезда будут соответствовать отрезкам [−23,73], [−8,−1] и [−113,−83], поэтому перейти дорогу в точке −1 возможно.

В момент времени 5 поезда будут соответствовать отрезкам [0,3], [−10,−3] и [−3,−2], поэтому перейти дорогу в точке −1 возможно.

0

WLRA, рассказывай. что не получается конкретно?

0