+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نقشه شازززلند به شکل یه مستطیل $A×B$ است. که گوشه های مقابلش $(0 ,0)$ و $(A, B)$ ان. شازززلند $n$ تا شهر داره که شهر $i$ ام در مختصات $ (x_i, y_i) $ قرار داره. به شهر $i$ میگیم غربی اگر و تنها اگر $x_i = 0$ و بهش میگیم شرقی اگر و تنها اگر $x_i = A$ شهر ها به وسیله $m$ جاده به هم وصل شدن. جاده ها به شکل خط های مستقیم در نقشه از یک شهر به شهر دیگری هستند. جاده ها یا یک طرفه اند یا دو طرفه. هیچ دو جاده ای همدیگه رو قطع نمی کنن. یعنی خط هاشون نقطه مشترک ندارن، مگر در شهر ها. شهردار شازززلند نقشه شازززلند رو به شما داده و از شما میخواد به ازای هر شهر غربی پیدا کنید به چند شهر شرقی مسیر داره. # ورودی در خط اول ورودی اعداد $n$ و $m$ و $A$ و $B$ آمده اند. $$1 \le n \le 300000$$$$0 \le m \le 900000$$$$1 \le A, B \le 10^9$$ در خط $i$ ام از $n$ خط بعدی $x_i$ و $y_i$ آمده اند. $$0 \le x_i \le A$$$$0 \le y_i \le B$$ در خط i ام از m خط بعدی $c_i$ و $d_i$ و $k_i$ آمده اند. $$1 \le c_i, d_i \le n$$$$1 \le k \le 2$$ اگر $k_i = 1$، جاده ای یک طرفه از شهر $c_i$ به شهر $d_i$ وجود دارد. در غیر این صورت، جاده ای دو طرفه بین شهر $c_i$ و $d_i$ وجود دارد. هیچ جاده ای بیشتر از یکبار در ورودی نیامده. می تونید فرض کنید حداقل یه راس غربی وجود داره که به حداقل یه راس شرقی مسیر داره. # خروجی باید به ازای هر شهر غربی چاپ کنید به چند شهر شرقی مسیر دارد. خروجی باید به ترتیب نزولی مختصات $y$ نقطه ها باشد. یعنی برای بالاترین شهر غربی در خط اول خروجی دومین بالا ترین شهر غربی در خط دوم خروجی و ... # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $$ n, m \le 6000 $$ | | ۲ | ۷۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 3 1 3 0 0 0 1 0 2 1 0 1 1 1 4 1 1 5 2 3 5 2 ``` ## خروجی نمونه ۱ ``` 2 0 2 ``` ## ورودی نمونه ۲ ``` 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 ``` ## خروجی نمونه ۲ ``` 4 4 0 2 ```  شهر در مختصات $ (0, 9)$ به $4$ شهر شرقی مسیر دارد. شهر در مختصات $ (0, 5)$ به $4$ شهر شرقی مسیر دارد. شهر در مختصات $ (0, 3)$ به $0$ شهر شرقی مسیر دارد. شهر در مختصات $ (0, 1)$ به $2$ شهر شرقی مسیر دارد.