B. Spyke чат
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компании R2 работает n сотрудников. В процессе работы постоянно нужно поддерживать связь, делиться достигнутыми успехами и обсуждать возникающие проблемы. Для этого R2 использует знаменитую программу Spyke для обмена мгновенными сообщениями.

Для обсуждения различных проектов у R2 есть m специальных Spyke чатов. В каждом чате ежедневно обменивается сообщениями некоторая группа сотрудников, при этом один сотрудник может одновременно состоять в нескольких чатах. Если какой-то сотрудник состоит в k-м чате, то он может писать сообщения в этот чат и получать уведомления о сообщениях из этого чата. Если сотрудник написал сообщение в чат, уведомление о нем приходит всем другим участникам чата.

В компании R2 проходит аудит. Сейчас специалисты занимаются изучением эффективности коммуникации сотрудников. Для этих целей у них есть лог сообщений и описание структуры чатов. Вам, как одному из специалистов по аудиту, поручено написать программу, которая по этим данным будет определять суммарное количество уведомлений о сообщениях, полученных каждым сотрудником.

Входные данные

В первой строке через пробел заданы три целых числа n, m и k (2 ≤ n ≤ 2·104; 1 ≤ m ≤ 10; 1 ≤ k ≤ 2·105) — количество сотрудников, количество чатов и количество событий в логе соответственно.

Далее в n строках задана матрица a размера n × m, состоящая из нулей и единиц. Элемент этой матрицы, записанный в j-м столбце i-й строки, (будем обозначать его aij) равен 1, если i-й сотрудник является участником j-го чата, в противном случае элемент равен 0. Считайте, что сотрудники пронумерованы от 1 до n, а чаты от 1 до m.

Далее в k строках задано описание событий лога. В i-й строке через пробел записаны два целых числа xi и yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m), которые обозначают, что сотрудник с номером xi отправил одно сообщение в чат под номером yi. Гарантируется, что сотрудник xi является участником чата yi. Гарантируется, что в каждом чате состоят хотя бы два сотрудника.

Выходные данные

В единственной строке через пробел выведите n целых чисел, где i-е число обозначает количество уведомлений о сообщениях, принятых i-м сотрудником.

Примеры
Входные данные
3 4 5
1 1 1 1
1 0 1 1
1 1 0 0
1 1
3 1
1 3
2 4
3 2
Выходные данные
3 3 1
Входные данные
4 3 4
0 1 1
1 0 1
1 1 1
0 0 0
1 2
2 1
3 1
1 3
Выходные данные
0 2 3 0