Прямоугольник и пути
У Степана через несколько минут свидание с Марисей, а он никак не может решить следующую задачу:
Дан прямоугольник размером a на b, противоположные углы которого имеют координаты (0, 0) и (a, b). Внутри прямоугольника расположены n точек, пронумерованных от 1 до n. Точка номер i имеет координаты (x[i], y[i]). Точки, координаты которых можно записать как (0, y), назовем левыми. Аналогично, точки вида (a, y) назовем правыми. Некоторые точки соединены отрезками, по которым можно перемещаться от точки к точке. По отрезку можно двигаться либо в обоих направлениях, либо только в одном, в зависимости от типа отрезка. Отрезки не имеют общих точек (пересечений, наложений), кроме концов отрезков.
Подсчитайте для каждой точки с левой стороны (пусть это точка q) количество точек с правой стороны, таких что из них можно добраться до точки q по отрезкам. Помогите ему!
Входные данные
В первой строке заданы 4 числа n, m, a, b — количество точек, количество отрезков и размеры прямоугольника (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 900 000, 1 ≤ a, b ≤ 10^9).
В следующих n строках заданы целые координаты точек в прямоугольнике. Никакие 2 точки не совпадают. Следующие m строки описывают отрезки тройками x, y, k (1 ≤ k ≤ 2). Если k = 1, то по отрезку можно двигаться только от точки x к y. Если k = 2, то по данному отрезку можно двигаться в обоих направлениях.
Выходные данные
Выведите ответ для каждой точки с левой стороны. Упорядочьте точки по убыванию y-координаты точек.