← 返回题目列表

Codeforces · 413/B

B. 斯派克聊天

中文机器翻译题面 查看原题

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