Задачі
Прямокутник та шляхи
Прямокутник та шляхи
У Степана через кілька хвилин побачення з Марисею, а він ніяк не може роз'язати наступну задачу:
Задано прямокутник розміру \textbf{a} на \textbf{b}, протилежні кути якого мають координати (\textbf{0},\textbf{ 0}) та (\textbf{a},\textit{\textbf{ }}\textbf{b}). У прямокутнику розташовано \textbf{n} точок, пронумерованих від \textbf{1} до \textbf{n}. Точка номер \textbf{i} має координати (\textbf{x}\[\textbf{i}\],\textbf{ y}\[\textbf{i}\]). Точки, координати яких можна записати як (\textbf{0},\textit{ }\textbf{y}), назвемо лівими. Аналогічно, точки вигляду (\textbf{a}, \textbf{y}) назвемо правими. Деякі точки з’єднані відрізками, по яких можна рухатись від точки до точки. По відрізку можна рухатись або в обох напрямках, або тільки в одному, залежно від типу відрізка. Відрізки не мають спільних точок (перетинів, накладань), окрім кінців відрізків.
Підрахуйте для кожної точки з лівої сторони (нехай це точка \textbf{q}) кількість точок з правої сторони, таких що з них можна добратись до точки \textbf{q} по відрізках. Допоможіть йому!
\InputFile
В першому рядку задано \textbf{4} числа \textbf{n, m, a, b} -- кількість точок, кількість відрізків, та розміри прямокутника (\textbf{1} ≤\textit{ }\textbf{n} ≤ \textbf{300 000}, \textbf{0} ≤ \textbf{m} ≤ \textbf{900 000, 1} ≤ \textbf{a, b} ≤ \textbf{10^9)}.
В наступних \textbf{n} рядках задано цілі координати точок в прямокутнику. Жодні \textbf{2} точки не співпадають. Наступні \textbf{m}\textit{\textbf{ }}рядків описують відрізки трійками \textbf{x}, \textbf{y}, \textbf{k} (\textbf{1} ≤ \textbf{k}\textit{ }≤ \textbf{2)}. Якщо \textbf{k}\textit{ }= \textbf{1}, то по відрізку можна рухатись лише від точки \textbf{x} до \textbf{y}. Якщо \textbf{k} = \textbf{2}, то по даному відрізку можна рухатись в обох напрямках.
\OutputFile
Виведіть відповідь для кожної точки з лівої сторони. Впорядкуйте точки за спаданням \textit{\textbf{y}}-координати точок.
Вхідні дані #1
12 13 7 9 0 1 0 3 2 2 5 2 7 1 7 4 7 6 7 7 3 5 0 5 0 9 3 9 1 3 2 3 2 1 3 4 1 4 5 1 5 6 1 9 3 1 9 4 1 9 7 1 9 12 2 10 9 1 11 12 1 12 8 1 12 10 1
Вихідні дані #1
4 4 0 2