ჭიანჭველები

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: cin

გამომავალი მონაცემები: cout

წყარო: IZHO, 2012


W x H სანტიმეტრის ზომის საკოორდინატო ბადეზე, რომლის საპირისპირო კუთხეების კოორდინატებია (0,0) და (W x H) მოძრაობს K ჭიანჭველა. ყოველ ჭიანჭველას შეუძლია იმოძრაოს 4–დან ერთ–ერთი მიმართულებით და იგი ყოველთვის გადის 1 სანტიმეტრს 1 წამში.

ჭიანჭველები ამაყი არსებები არიან და არასოდეს უთმობენ გზას ერთმანეთს, ამიტომ თუ ისინი ერთმანეთს შუბლებით შეასკდებიან, მომენტალურად შეტრიალდებიან და საპირისპირო მიმართულებით იწყებენ მოძრაობას. ჭიანჭველები ანალოგიურად იქცევიან, თუკი ისინი მიაღწევენ არის საზღვრებს, ხოლო თუკი ისინი ერთმანეთის პერპენდიკულარულად მოძრაობენ და ერთ უჯრაში აღმოჩნდებიან, ერთმანეთს ყურადღებას არ აქცევენ (შესაბამისი შემთხვევები განხილულია მაგალითებში).

თქვენ გეძლევათ ყველა ჭიანჭველის საწყისი მდებარეობა და მოძრაობის მიმართულება დროის რაღაც მომენტში. განსაზღვრეთ მათი მდებარეობა და მოძრაობის მიმართულება T წამის შემდეგ.

 

შემავალი მონაცემები

პირველ სტრიქონში ოთხი მთელი რიცხვი W,H, K და T (1 <= W,H,K <= 100, 1 <= T <=109).

მომდევნო K სტრიქონიდან თითოეულში მოცემულია 3 მთელი რიცხვი: Xi, Yi, Di, სადაც (Xi, Yi) ჭიანჭველი კოორდინატებია, ხოლო Di – მოძრაობის მიმართულებაა (0< Xi <W, 0< Yi < H, 1 <= Di <=4). Di=1, თუ ჭიანჭველა მოძრაობს X–ის ზრდის მიმართულებით, Di=2, – Y–ის ზრდის მიმართულებით, Di=3, – X –ის კლების მიმართულებით, Di=4, – Y –ის კლების მიმართულებით.

სტრიქონებში რიცხვები ჰარითაა გაყოფილი. ყველა ჭიანჭველა განსხვავებულ წერტილში იმყოფება.

 

გამომავალი მონაცემები

ზუსტად K ცალი სტრიქონიდან თითოეულში უნდა იყოს ინფორმაცია თითოეულ ჭიანჭველაზე იმავე თანმიმდევრობით, როგორიც ის შემომავალ ფაილში იყო მოცემული. ყოველი სტრიქონი უნდა შეიცავდეს 3 მთელ რიცხვს – ჭიანჭველას ორ კოორდინატს და მისი მოძრაობის მიმართულებას.




მაგალითები

შესატანი მონაცემები
4 4 2 3 1 1 1 3 3 4 დაკოპირება
გამოსატანი მონაცემები
4 1 3 3 0 2 დაკოპირება
შესატანი მონაცემები
4 4 2 4 1 1 1 3 3 4 დაკოპირება
გამოსატანი მონაცემები
3 1 3 3 1 2 დაკოპირება
შესატანი მონაცემები
4 4 2 2 1 1 1 3 1 3 დაკოპირება
გამოსატანი მონაცემები
1 1 3 3 1 1 დაკოპირება
შესატანი მონაცემები
4 4 2 2 2 1 1 3 1 3 დაკოპირება
გამოსატანი მონაცემები
1 1 3 4 1 3 დაკოპირება

შენიშვნა

ტესტების 70%–სათვის 1< T <10 000.