Düzbucaqlı və yollar
Степanın bir neçə dəqiqədən sonra Marisə ilə görüşü var, amma o, növbəti məsələni həll edə bilmir:
Ölçüsü a x b olan düzbucaqlı verilib, əks künclərinin koordinatları (0, 0) və (a, b) olan. Düzbucaqlıda n nöqtə yerləşdirilib və bu nöqtələr 1-dən n-ə qədər nömrələnib. i-ci nöqtənin koordinatları (x[i], y[i]) şəklindədir. Koordinatları (0, y) olan nöqtələrə sol nöqtələr deyəcəyik. Eyni şəkildə, (a, y) olan nöqtələrə sağ nöqtələr deyəcəyik. Bəzi nöqtələr bir-birinə seqmentlərlə birləşdirilib və bu seqmentlər vasitəsilə nöqtədən nöqtəyə hərəkət etmək mümkündür. Seqmentlərdən biri ilə hər iki istiqamətdə və ya yalnız bir istiqamətdə hərəkət etmək olar, bu seqmentin növündən asılıdır. Seqmentlərdə seqmentlərin ucları xaricində ortaq nöqtələr (kəsişmələr, üst-üstə düşmələr) yoxdur.
Sol tərəfdəki hər bir nöqtə üçün (bu nöqtə q olsun) sağ tərəfdəki nöqtələrin sayını hesablayın ki, bu nöqtələrdən q nöqtəsinə seqmentlər vasitəsilə çatmaq mümkün olsun. Ona kömək edin!
Giriş verilənləri
Birinci sətirdə 4 ədəd n, m, a, b verilib – nöqtələrin sayı, seqmentlərin sayı və düzbucaqlının ölçüləri (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 900 000, 1 ≤ a, b ≤ 10^9).
Növbəti n sətirdə düzbucaqlıda nöqtələrin tam ədədi koordinatları verilib. Heç bir 2 nöqtə üst-üstə düşmür. Növbəti m sətir seqmentləri x, y, k üçlükləri ilə təsvir edir (1 ≤ k ≤ 2). Əgər k = 1 olarsa, seqmentdən yalnız x nöqtəsindən y nöqtəsinə hərəkət etmək olar. Əgər k = 2 olarsa, bu seqmentdən hər iki istiqamətdə hərəkət etmək olar.
Çıxış verilənləri
Sol tərəfdəki hər bir nöqtə üçün cavabı çıxarın. Nöqtələri y koordinatına görə azalan sırada düzün.