Найгірший сценарій
Хвороба стрімко поширюється, і уряд потребує карти заражених регіонів. Їх цікавить, як виглядатимуть певні регіони в найгіршому випадку, враховуючи певну послідовність подій. Існує чотири стадії інфекції, які цікавлять владу.
**Стадія A**
Інфекція ще не досягла цієї зони. Є ймовірність, що такі зони можуть перейти на вищу стадію інфекції через подію зараження.
**Стадія B**
Ця зона знаходиться на ранніх стадіях інфекції. Є повідомлення про непередбачувану поведінку окремих громадян, починаються карантини, і муніципальна влада ще контролює ситуацію.
**Стадія C**
Ця зона має справу з натовпами зомбі в кількох районах. Карантини відбуваються на рівні міст і малих містечок. Інфекція обмежена зоною, але виходить з-під контролю.
**Стадія D**
Ця зона втратила контроль над своїми кордонами. Це лише питання часу, коли інфекція пошириться на сусідні зони.
Подія зараження — це будь-що, що змушує зону перейти на вищу стадію інфекції. Це зазвичай результат прориву карантину, мутації вірусу або біологічного тероризму. Коли подія зараження відбувається в зоні, вона, в найгіршому випадку, змусить зону перейти на вищу стадію. Зона на стадії **D** не може перейти на вищу стадію і, в найгіршому випадку, призведе до спалаху для кожної додаткової події зараження, яку вона переживає. Коли відбувається спалах, усі сусідні зони переживають додаткову подію зараження. Спалах може викликати ланцюгову реакцію спалахів, але спалах може викликати максимум один спалах у кожній зоні.
Зони, позначені символом **X**, є непрохідними та незаселеними територіями, які не можуть бути заражені. Сусідня зона — це одна зона вище, нижче, зліва або справа на сітці зон. Під час спалаху інфекція не може поширюватися по діагоналі.
Ви отримаєте сітку зон з їх початковими стадіями та послідовність подій зараження з координатами зон, в яких вони відбуваються. Кожна подія зараження повинна бути оброблена перед обчисленням результату наступної події зараження.
Вхідні дані
Перша строка вхідних даних міститиме кількість тестових випадків, **N** (1 ≤ **N** ≤ 50). Кожен тестовий випадок починатиметься зі строки, що вказує ширину, **W** (1 ≤ **W** ≤ 100) і висоту, **H** (1 ≤ **H** ≤ 100) сітки, після чого йде сама сітка. Кожна зона в сітці буде позначена стадією, на якій вона зараз знаходиться, або символом **X**, якщо зона непрохідна.
Після сітки буде строка з кількістю подій зараження **I** (0 ≤ **I** ≤ 1000). **I** строк слідуватимуть, кожна з яких міститиме координати **X** та **Y** зони. Кожна строка представляє подію зараження, що відбувається в **X**-му стовпці (лівий стовпець є **X = 0**) та **Y**-му рядку (верхній рядок є **Y = 0**).
Вихідні дані
Ваш вихід повинен показати кожну сітку з її станами, якщо відбудеться найгірший сценарій.