Условие

---

ЗАДАЧА L. НАНО БОМБИ
---
Биотехнологична лаборатория разработва нов продукт за почистване на биологична среда от вредни организми. Задачата Ви е да разработите софтуерен симулатор на тестова среда, в която ще се изпълняват серия от експерименти.

Биологичната среда се разделя на правоъгълна мрежа от квадратни клетки с еднаква големина. Всяка клетка се идентифицира с двойка координати (x, y), които започват от (1, 1) и нарастват надясно и надолу.

Клетките, в които живеят вредни организми, се маркират като заразени и се обстрелват с поредица от нано бомби. Всяка бомба се активира в центъра на дадена клетка, в резултат на което се изстрелват 4 почистващи частици, в четирите посоки (нагоре, надолу, наляво и надясно), вертикално и хоризонтално по мрежата.

Всяка частица достига до средата на съседната клетка за време Т и продължава да се движи в същата посока и със същата скорост, докато:
- Попадне в заразена клетка. В тази ситуация, частицата спира да се движи и преминава в режим на почистване.
- Излезе от наблюдаваната мрежа от клетки, при което спираме да се интересуваме от нейното движение.
- Удари друга частица. Това се случва, когато двете частици достигнат до средата на една и съща клетка по едно и също време или когато се движат една към друга и се срещнат на границата на две съседни клетки. В тази ситуация, частицата, която е изстреляна по-скоро, унищожава другата и продължава нормалното си движение.

Ако нано бомба бъде активирана в заразена клетка, частиците не успяват да наберат потенциал и не оказват влияние на резултата. Ако бомба бъде активирана в клетка, в която в същия момент е достигнала частица, новоизстреляните частици унищожават по-старата.

Всеки експеримент се разделя на равни времеви етапи с продължителност Т (времето на придвижване на частица между две съседни клетки). В началото на всеки етап се активира точно една нано бомба в някоя от клетките на мрежата.

Експериментът приключва, когато няма движещи се частици в наблюдаваната среда. Задачата на симулатора е да изчисли колко от изстреляните частици са в режим на почистване и в кои заразени клетки.

Вход:
- На първия ред се задават 4 цели числа, разделени с интервали - широчината (W) и височината (H) на мрежата в брой клетки, броят заразени клетки (I) и броят на активираните бомби (B).
- На следващите I реда се задават двойки цели числа (x, y), разделени с интервал - координати на заразена клетка.
- На следващите B реда се задават двойки цели числа (x, y), разделени с интервал - координати на активирана нано бомба. Бомбите се активират в зададения ред, последователно, в началото на всеки времеви интервал от експеримента.

Изход:
На всеки ред трябва да се изведат 3 цели числа, разделени с интервал - първите две са координати на заразена клетка, а третото е броя на почистващите частици в нея. Не трябва да се извежда информация за клетки без действащи частици в тях. Заразените клетки трябва да са подредени в същия ред, в който са зададени от входа.

Ограничения:
0 < W, H, x, y <= 300 000; 
0 < I < 100; 
0 < B < 100.

Примерен вход:
10 10 4 4
4 2
1 3
4 3
2 4
2 1
3 3
2 3
4 3	

Примерен изход:
1 3 1
4 3 2
2 4 1