R2 公司有 n 名员工。这项工作涉及不断交流想法、分享成功故事和即将到来的挑战。为此,R2 使用了著名的即时通讯程序 Spyke。
R2 有 m 个 Spyke 聊天,只是为了讨论各种问题。在每次聊天中,一些员工每天都会交换消息。员工可以同时在多个聊天中交谈。如果某个员工在第 k 个聊天中,他可以向该聊天写入消息并接收有关来自该聊天的消息的通知。如果员工在聊天中写入消息,则聊天的所有其他参与者都会收到消息通知。
R2 公司正在进行审计。现在专家们研究员工之间的有效沟通。为此,他们有聊天日志和聊天结构的描述。作为审计专家之一,您被委托编写一个程序,该程序将使用此数据来确定每个员工收到的消息通知的总数。
输入
第一行包含三个空格分隔的整数 n、m 和 k (2 ≤ n ≤ 2·104; 1 ≤ m ≤ 10; 1 ≤ k ≤ 2·105) — 相应地,员工数量、聊天数量和日志中的事件数量。
接下来的 n 行包含大小为 n × m 的矩阵 a,由数字 0 和 1 组成。如果第 i 个员工是第 j 个聊天的参与者,则该矩阵的元素(记录在第 i 行的第 j 列(我们将其表示为 aij))等于 1,否则该元素等于 0。假设员工编号为 1 到 n,聊天编号为 1 到 m。
接下来的 k 行包含日志事件的描述。第 i 行包含两个空格分隔的整数 xi 和 yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m),这意味着员工号码 xi 向聊天号码 yi 发送了一条消息。保证编号xi的员工是聊天yi的参与者。保证每次聊天至少包含两名员工。
输出
单行打印n个空格分隔的整数,其中第i个整数表示第i个员工收到的消息通知的数量。
示例
输入 #1
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
输出 #1
3 3 1
输入 #2
4 3 4 0 1 1 1 0 1 1 1 1 0 0 0 1 2 2 1 3 1 1 3
输出 #2
0 2 3 0