Kübik Yerdə Qarışqalar#4884
Bu məsələ Yer səthi kub şəklində götürülür, kubun hər üzü m \times m ölçüsündə kvadratdır və 1 \times 1 ölçülü hüceyrələrə bölünür.
İlk olaraq, qarışqa bu kubun yuxarı üzündə yerləşir. Hər bir qarışqa dörd istiqamətdən birinə: şimal, cənub, qərb və ya şərqə baxır.
Bir anda bütün qarışqalar hərəkətə başlayır və hər biri baxdığı istiqamətdə düz xətt üzrə irəliləyir. Qarışqa kubun kənarına çatanda, növbəti üzə keçir və hərəkət etdiyi istiqamət kəsişdiyi kənara perpendikulyar olur.
Bu hərəkət sonsuz müddət davam edir. Tapşırığınız budur ki, bu proses zamanı heç bir qarışqanın keçmədiyi hüceyrələrin sayını müəyyən edəsiniz.
Girişin birinci sətrində Yer üzərindəki qarışqaların sayı və kubun hər tərəfinin uzunluğu olan iki natural ədəd və verilir (1 \leq n \leq 100\,000; 1 \leq m \leq 15\,000).
Növbəti sətrin hər birində bir qarışqanın ilkin mövqeyi verilir. Sətrdə iki natural ədəd və (qarışqanın yuxarı üzdəki koordinatları), sonra isə istiqaməti göstərən bir simvol olur: 'N', 'S', 'W', yaxud 'E'. Rəqəmlərlə simvol arasında dəqiq bir boşluq olur.
Koordinat oxları və kubun üzlərinin istiqamətləri şəkildə göstərilib. Bütün koordinatlar -dən -ə qədər (hər ikisi daxil olmaqla) dəyişir.
Başlanğıcda və ya hər hansı başqa anda bir hüceyrədə bir neçə qarışqa ola bilər və bu, onların hərəkətinə təsir etmir.
Bir ədəd çıxışa yazın: qarışqaların heç vaxt daxil olmadığı hüceyrələrin sayını.
Nümunə 1