Прямокутник та шляхи
У Степана через кілька хвилин побачення з Марисею, а він ніяк не може роз'язати наступну задачу:
Задано прямокутник розміру 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-координати точок.