Qarışqalar

Koordinat şəbəkəsində əks küncləri (0, 0) və (w, h) nöqtələrində yerləşən düzbucaqlı bir sahə var. Bu sahənin içində şəbəkə xətləri boyunca k qarışqa qaçır. Hər qarışqa 4 istiqamətdən birində və saniyədə 1 hüceyrə sürətlə hərəkət edə bilər.

Qarışqalar çox qürurlu varlıqlar olduğundan, heç vaxt yoldan çəkilmirlər. Buna görə, iki qarışqa üz-üzə toqquşduqda, dərhal geri dönüb əks istiqamətdə hərəkət etməyə davam edirlər. İki qarışqa perpendikulyar qaçdıqda isə bir-birinə heç bir diqqət yetirmirlər. Qarışqa sahənin sərhədinə çatdıqda da geri dönüb geri qaçır.

Başlanğıc anında bütün qarışqaların mövqeyi və hərəkət istiqaməti verilir. t saniyə sonra onların mövqeyini və hərəkət istiqamətini müəyyən edin.

Giriş məlumatları

Birinci sətir 4 tam ədədi ehtiva edir: w, h, k, t (1 ≤ w, h, k ≤ 100, 1 ≤ t ≤ 10^9).

Növbəti k sətirin hər biri 3 tam ədəd ehtiva edir: x[i], y[i], d[i], burada (x[i], y[i]) qarışqanın koordinatları, d[i] isə onun hərəkət istiqamətidir (0 < x[i] < w, 0 < y[i] < h, 1 ≤ d[i] ≤ 4). d[i] = 1, əgər qarışqa x-in artma istiqamətində hərəkət edirsə, d[i] = 2 - y-in artma istiqamətində, d[i] = 3 - x-in azalma istiqamətində, d[i] = 4 - y-in azalma istiqamətində.

Bütün ədədlər sətirlərdə boşluqla ayrılıb. Bütün qarışqalar fərqli nöqtələrdədir.

Çıxış məlumatları

Dəqiq k sətir çıxarın - girişdəki məlumatların verildiyi sırada hər qarışqa üçün bir sətir. Hər sətir qarışqanın koordinatlarını və hərəkət istiqamətini ehtiva edən 3 tam ədəd, boşluqla ayrılmış olmalıdır.