Кунай
Kunaı, ninjaların istifadə etdiyi bıçaq şəklində bir silahdır. Ninjalar düşmənə hücum edərkən, kunaını atırlar.
w sütun və h sıradan ibarət olan bir şəbəkədə n ninja var. Hər ninja bir hüceyrənin mərkəzində yerləşir və heç bir iki ninja eyni hüceyrədə yerləşmir. Hər ninjanın bir kunaısı var və hər biri dörd istiqamətdən birinə baxır: yuxarı, aşağı, sola və ya sağa. 0 zaman anında, hər ninja baxdığı istiqamətə kunaını atır.
Hər kunaı düz xətt üzrə 1 sürətlə hərəkət edir. Əgər bir neçə kunaı eyni anda bir nöqtəyə çatarsa, onlar bir-birinə dəyir və yox olurlar. Kunaının ölçüsü o qədər kiçikdir ki, biz onu nəzərə almaya bilərik. Həmçinin, ninjalar sürətlə hərəkət edə bildikləri üçün, kunaı onlara dəyməyəcək. Hər kunaı düz xətt üzrə uçur, sürətini itirmədən, başqa bir kunaı ilə toqquşana qədər.
Aşağıdakı şəkillərdə oxlar kunaıları göstərir. Oxların istiqaməti kunaıların hərəkət istiqamətidir. Bu şəkillərdə bütün qalın oxlar toqquşacaq.
Aşağıdakı şəkillərdə qalın oxlar toqquşmayacaq. İkinci və üçüncü şəkillərdə incə ox qalın oxla toqquşacaq. Toqquşan oxlar yox olduqdan sonra, hər bir bu şəkillərdə qalın ox başqa bir oxla toqquşmayacaq.
Tapşırıq
Kunaıların kifayət qədər vaxt keçdikdən sonra keçəcəyi hüceyrələrin sayını hesablayın.
Məhdudiyyətlər
1 ≤ n ≤ 100000 - ninjaların sayı 1 ≤ w ≤ 1000000000, 1 ≤ h ≤ 1000000000 - şəbəkənin ölçüləri 1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h - ninjaların koordinatları
Giriş verilənləri
Birinci sətir şəbəkənin ölçülərini təsvir edən iki tam ədəd w və h ehtiva edir. İkinci sətir ninjaların sayını göstərən n ədədini ehtiva edir. Sonra n sətir gəlir. i-ci sətir (1 ≤ i ≤ n) üç tam ədəd, boşluqla ayrılmış: x_i, y_i, d_i ehtiva edir ki, bu da i-ci ninjanın mövqeyini (soldan x_i sütunu və yuxarıdan y_i sırası) və onun istiqamətini d_i göstərir. Heç bir iki ninja eyni mövqedə yerləşmir. d_i dəyərləri aşağıda təsvir edilmişdir:
Əgər d_i = 0, onda i-ci ninja sağa baxır.
Əgər d_i = 1, onda i-ci ninja yuxarı baxır.
Əgər d_i = 2, onda i-ci ninja sola baxır.
Əgər d_i = 3, onda i-ci ninja aşağı baxır.
Çıxış verilənləri
Kifayət qədər vaxt keçdikdən sonra kunaıların keçəcəyi w×h şəbəkəsindəki hüceyrələrin sayını çıxarın.
Misal 1 üçün qeyd
0 zaman anında şəbəkə aşağıdakı kimi görünür:
i-ci ninjanın atdığı kunaı i ilə göstərilir. 0.5 zaman anında, 2 və 3 kunaıları toqquşacaq və yox olacaq. Aşağıdakı şəkil 1 zaman anını təsvir edir. Boz hüceyrələr kunaıların artıq keçdiyi hüceyrələri göstərir.
2 zaman anında, 1 və 5 kunaıları toqquşacaq və yox olacaq. 2 zaman anında şəbəkə aşağıda təsvir edilmişdir.
2 zaman anından sonra heç bir kunaı daha toqquşmayacaq. Kifayət qədər vaxt keçdikdən sonra şəbəkə aşağıdakı kimi görünəcək:
Nəticədə, kunaıların keçdiyi hüceyrələrin sayı 11-dir. Buna görə də biz 11 ədədini çıxmalıyıq.