Подарунки з чемпіонату

Обмеження часу процесора 0,5 секунди

Обмеження на використання пам'яті 256 мегабайтів

На планеті Бітакуляндії є щорічне престижне змагання, яке проводить Міс М, — міжнародний командний чемпіонат.

У цьому змаганні беруть участь жителі з усіх країн Бітакуляндії. На чемпіонаті також треба розв'язувати задачки з дуже цікавою легендою, як ця, але в командах. Найкращим командам за підсумками чемпіонату видаються призи.

Міс М нарешті прийшли довгоочікувані подарунки для чемпіонату, які треба відправити переможцям. Вона зрозуміла, що подарунків багато. І якщо з чашками та пакетиками все зрозуміло, то з футболками виникла проблема. Кожна команда має трьох учасників, і кожен з них замовив футболку одного з $n$ кольорів та одного з $m$ розмірів. Але Міс М не впевнена, що всі побажання переможців будуть виконані...

Тому Міс M розробила алгоритм, згідно з яким буде збирати подарунки для учасників.

Якщо футболка потрібного розміру та кольору ще залишилась, то вона її бере.
У протилежному випадку — шукає футболку того ж розміру, але іншого кольору. Якщо таких кілька, то колір з мінімальним номером.
Інакше шукаємо серед футболок наступного більшого розміру, але з пріоритетом кольору, який було вказано учасником на початку. Якщо немає футболки з пріоритетним кольором, але є кілька інших, то вибираємо футболку з мінімальним номером.
Інакше повторюємо процес попереднього пункту серед футболок наступного більшого розміру. Так повторюємо доти, доки такі розміри є.
Якщо ніяка футболка з тих, що залишилися, не підійшла, то футболку, яку вказав учасник, записують як відсутню.

Міс М вирішила, що треба відправити назад на склад футболки, які виявилися зайвими, та замовити ще ті футболки, які вона записала як відсутні, щоб задовольнити всіх переможців чемпіонату. Щоб не розкладати всі футболки власноруч, Міс M просить вас написати програму, яка:

Виводить, які саме футболки виявилися зайвими, у форматі таблиці розміром $n \times m$ , де $l_{ij}$ — кількість футболок $i$ -го кольору та $j$ -го розміру, які залишилися після того, як вона роздала всім учасникам футболки.
Виводить, які футболки треба замовити у форматі таблиці розміром $n \times m$ , де $n_{ij}$ — кількість футболок $i$ -го кольору та $j$ -го розміру, які попросили учасники, але організатори не змогли дати будь-які футболки.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ( $1 \leq n \leq 100, 1 \leq m \leq 6$ ) — кількість різних кольорів та розмірів футболок відповідно.

Другий рядок містить $m$ елементів — розміри футболок, які доставили Міс М. Розміри бувають — XS, S, M, L, XL, 2XL. Гарантується, що розміри даються в порядку зростання розмірів.

Кожен з наступних $n$ рядків містить по $m$ цілих чисел $t_{i 1}, t_{i 2}, \dots, t_{im}$ ( $0 \leq t_{ij} \leq 5 \cdot 1 0^{3}$ ) — кількість футболок $i$ -го кольору та $j$ -го розміру.

Наступний рядок містить одне ціле число $k$ ( $1 \leq k \leq 1 0^{5}$ ) — кількість переможців.

Кожний з наступних $k$ рядків містять по цілому числу $c_{i}$ ( $1 \leq c_{i} \leq n$ ) та символу $s_{i}$ — колір та розмір кожної футболки відповідно. Гарантується, що $s_{i}$ — один з $m$ розмірів, який був заданий.

Обробляти запити переможців треба саме в такому порядку, як зазначено.

Вихідні дані

У кожному з наступних з $n$ рядків виведіть по $m$ цілих чисел $l_{i 1}, l_{i 2}, \dots, l_{im}$ — кількість футболок $i$ -го кольору та $j$ -го розміру, які залишилися.

У кожному з наступних з $n$ рядків виведіть по $m$ цілих чисел $n_{i 1}, n_{i 2}, \dots, n_{im}$ — кількість футболок $i$ -го кольору та $j$ -го розміру, які потрібно докупити.

Приклади

Вхідні дані

Відповідь

Примітка

Припустимо, що в нас є білі футболки (індекс один) та чорні футболки (індекс два). Отже, у нас є одна біла футболка розміру S, а також три білі футболки розміру M. Є три чорні футболки розміру S, а також три чорні футболки розміру XL.

Розглянемо кожного переможця:

Переможцю потрібна біла футболка розміру S, у нас така є, тому ми її йому видаємо. Це була остання така футболка.
Переможцю потрібна чорна футболка розміру XL, у нас така є, тому ми її йому видаємо. У нас залишається ще дві такі футболки.
Переможцю потрібна біла футболка розміру M, у нас така є, тому ми її йому видаємо. У нас залишається ще дві такі футболки.
Переможцю потрібна чорна футболка розміру XL, у нас така є, тому ми її йому видаємо. У нас залишається ще одна така футболка.
Переможцю потрібна біла футболка розміру M, у нас така є, тому ми її йому видаємо. У нас залишається ще одна така футболка.
Переможцю потрібна чорна футболка розміру M, у нас такої немає. Проте у нас є біла футболка розміру M, тому ми її йому видаємо. У нас більше не залишається білих футболок розміру M.
Переможцю потрібна біла футболка розміру M, у нас такої немає. У нас також немає чорної футболки розміру M, тому ми не можемо видати переможцю футболку розміру M. Через те дивимося на наступний розмір — XL. Переможець хоче отримати саме білу футболку, але такої футболки розміру XL у нас також немає. Тому ми видаємо йому чорну футболку розміру XL. Це була остання така футболка.
Переможцю потрібна чорна футболка розміру S, у нас така є, тому ми її йому видаємо. У нас залишається ще одна така футболка.
Переможцю потрібна біла футболка розміру XL, проте у нас немає ні білої футболки такого розміру, ні чорної. Через те, що в нас немає футболок більшого розміру, ми не можемо учаснику видати футболку, яку він вказав, ми записуємо її у список.

У нас залишається дві чорні футболки розміру S.

Ми не змогли видати одну білу футболку розміру XL.

Відправки 13

Коефіцієнт прийняття 15%