The 10th Jimei University Programming Contest
A. A+B问题
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小M有两个X( ≤ 16)进制非负整数A，B并知道它们的和S = A + B（用X进制表示），但是他忘记了X是几，现在请你帮帮小M。

如果有多种可能的X你只需要输出任意一种即可，保证有解

Input

每个测试点共 T( ≤ 105) 组数据。 对于每组数据，输入一行三个非负X进制整数 A, B, S(A, B ≤ 28)。 （其中，如果0 - 9不足以表示，使用大写字母'A'-'F'表示10 - 15）

Output

对于每组数据，输出一行一个正整数代表你求出的X。

Example
Input
2
F F 1E
1 1 2
Output
16
3

B. 看比赛
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

今天是第十届集美大学程序设计竞赛的决赛日，小M和小I约定好了要来看比赛。

小M将厦门市抽象为了一个 N 个点 M 条边的无向带权联通图，他们要从厦门大学（1 号点）走到集美大学（N号点）观看比赛。 为了增加路途中的趣味性，小M决定和小I玩一个游戏，他们要轮流指定走到的下一条路，走到集美大学时轮到谁指定怎么走，谁就输了，小M先走。

当然，他们不想因为博弈错过了大家精彩的比赛，所以他们一定会确保每次选择的走的路是能够最快到达集美大学的路。 小M和小I都十分的聪明，所以他们都会按照最优策略来选择如何走。

现在小M想要知道，他是否能够获胜。

Input

输入第一行是一个正整数 T, 表示本题共有 T( ≤ 10) 组数据， 对于每组数据，第一行是两个被空格分隔的正整数 N( ≤ 105), M( ≤ 2 × 105)。

接下来 M 行，每行三个被空格分隔的正整数 ui, vi, wi，表示在 ui, vi( ≤ N) 之间有一条边，小M和小I需要花 wi( ≤ 109) 的时间走过。

Output

每组数据输出一行，如果小M获胜，输出 "Little M is the winner." 否则输出 "Little I is the winner."。

Example
Input
2
2 1
1 2 1
3 3
1 2 1
2 3 1
1 3 3
Output
Little M is the winner.
Little I is the winner.

C. 方格染色
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小 Z 正在处理染色问题！问题发生在一个由 2 × n 个 1 × 1 的小正方形方格组成的矩形纸条上，小 Z 想要把矩形纸条的每个方格染成黑色或是白色。

但由于小 Z 的视力不太好，若相邻两个方格都是黑色，小 Z 会非常困惑。因此。她希望最后染色方案中任意两个黑色方格均不相邻。同时，她还想知道在黑色方格恰好有 k 个的情况下，求出满足上述条件的染色方案数对 998244353 取模的结果？

Input

每个测试点包含多组测试数据。

第一行包含一个正整数 T（1 ≤ T ≤ 105），表示测试数据组数。

每组测试数据共一行，包含两个用空格分隔的非负整数 n, k（1 ≤ n ≤ 105, 0 ≤ k ≤ 105），分别表示矩形纸条的长度以及黑色方格数。

保证所有测试数据组数的 k 之和 。

Output

对于每组数据组数，输出一行一个整数，表示满足题目条件的染色方案数对 998244353 取模的结果。

Example
Input
4
4 2
3 0
6 5
5 7
Output
18
1
20
0

D. 划分平面
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小M给了你一个平面，在这个平面上，有 N 个村庄，第 i 个村庄的坐标记为 xi, yi。

小M想要将这 N 个村庄划分为两个国家，由于两个国家之间必须要有口岸，于是小M决定要求你找到一条过两个村庄的直线，以这条直线作为国界，以这两个村庄作为两个国家的口岸（直线上的所有村庄视为两个国家各占一半，但口岸只有两个）。

小M还希望这两个国家的势力相当，因此小M希望，两个国家的村庄数量要相等。

小M想要考考你，小M有多少种划分口岸的方法呢？（两种方法不同，当且仅当选择的口岸村庄不完全相同。）

Input

输入的第一行为一个正整数 N(2 ≤ N ≤ 2 × 103)，表示一共有 N 个点。

接下来 N 行，每行两个整数 xi, yi(|xi|, |yi| ≤ 109)，表示这 N 个点的坐标。

保证没有任意两个村庄重合。

Output

输出一行一个整数表示划分口岸的方法。

Example
Input
5
0 0
1 1
-1 1
1 -1
-1 -1
Output
6

E. 时间超限α
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

注意：本题与β 版本仅有问题描述的最后一段及输出要求不同，其余均相同。

在ICPC2021南京站，比赛进行到了4:58:24时，小M提交了E题的代码。

他看到了"等待评测（还有1000+提交）"的时候，不禁开始担心，我这份代码能否通过(Accepted)呢？会不会因为评测机波动导致超时(Time Limit Exceeded)不能通过呢？

小M已经知道，本次比赛一共有 N 台评测机，其中第 i 台评测机一共有 ki 个可供评测的线程，为了方便大家签到，我们不妨假设这 ki 个线程是一样的。

我们知道，多线程评测时的运行速度通常会低于单线程的评测速度，我们记第 i 台评测机在使用 j 个线程时，各个线程的运行小M的代码所需的时间为 tj(i)。

现在已知小M提交代码进入评测后台时一共有 M 份代码被一起评测，后台会等概率将代码分配到任意评测机上（只要不超过这个评测机的线程限制）。 由于小M是个非洲人，请你计算最坏情况下，小M的代码需要运行多久。

Input

输入的第一行为一个正整数 N( ≤ 2 × 103)，表示一共有 N 台评测机。

接下来 N 行，每行首先是一个正整数 ki，表示第 i 台评测机一共有 ki 个可供评测的线程， 接下来 ki 个正整数 tj(i)( ≤ 109)，第 j 个正整数表示第 i 台评测机在使用 j 个线程时，各个线程的运行小M的代码所需的时间。 （保证 ） 最后一行为一个正整数 ，表示小M提交代码进入评测后台时一起评测的代码数。

Output

输出一行一个正整数，表示最坏情况下，小M的代码需要运行多久。

Example
Input
3
2 1 5
3 1 2 5
1 2
3
Output
5

F. 时间超限β
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

注意：本题与α 版本仅有问题描述的最后一段及输出要求不同，其余均相同。 在ICPC2021南京站，比赛进行到了4:58:24时，小M提交了E题的代码。

他看到了"等待评测（还有1000+提交）"的时候，不禁开始担心，我这份代码能否通过(Accepted)呢？会不会因为评测机波动导致超时(Time Limit Exceeded)不能通过呢？

小M已经知道，本次比赛一共有 N 台评测机，其中第 i 台评测机一共有 ki 个可供评测的线程，为了方便大家签到，我们不妨假设这 ki 个线程是一样的。

我们知道，多线程评测时的运行速度通常会低于单线程的评测速度，我们记第 i 台评测机在使用 j 个线程时，各个线程的运行小M的代码所需的时间为 tj(i)。

现在已知小M提交代码进入评测后台时一共有 M 份代码被一起评测，后台会等概率将代码分配到任意评测机上（只要不超过这个评测机的线程限制）。形式化地，等概率是指考虑一个序列{ai}，表示第i个评测机上分配了ai(0 ≤ ai ≤ ki)个代码进行评测，我们考虑在所有的的序列中等概率随机。

请你计算所有情况下，小M的代码需要运行的时间之和。由于答案可能很大，请你对 109 + 7 取模。

请注意：在本题中，我们认为小M的代码以外的代码之间没有区别。

Input

输入的第一行为一个正整数 N( ≤ 2 × 103)，表示一共有 N 台评测机。

接下来 N 行，每行首先是一个正整数 ki，表示第 i 台评测机一共有 ki 个可供评测的线程， 接下来 ki 个正整数 tj(i)( ≤ 109)，第 j 个正整数表示第 i 台评测机在使用 j 个线程时，各个线程的运行小M的代码所需的时间。 （保证 ） 最后一行为一个正整数 ，表示小M提交代码进入评测后台时一起评测的代码数。

Output

输出一行一个正整数，表示所有情况下，小M的代码需要运行的时间之和。（由于这个答案可能很大，请你对 109 + 7 取模后输出。）

Example
Input
2
2 1 2
1 1
2
Output
4

G. 我要成为宝可梦大师！
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Pecco是一名宝可梦训练家，今天他和他的朋友Index进行宝可梦对战。

一只宝可梦有六项能力值：HP、物攻，物防，特攻，特防，速度。此外宝可梦具有1到2种属性。

因为Pecco和Index都只带了一只50级的宝可梦，所以我们把他们的对战过程简化如下：

首先，速度较快的一方打出招式，之后两只宝可梦轮流打出招式（保证双方的速度不同）。招式分为物理招式和特殊招式，并具有固定的属性、威力和命中率。使用招式后，先按照命中率计算能否命中，如果命中，可以使对方受到伤害（HP降低），伤害按以下公式计算：

其中：

  • 当招式是物理招式时，A和D分别表示招式打出者的物攻和承受者的物防；当招式是特殊招式时，A和D分别表示招式打出者的特攻和承受者的特防。
  • P 表示技能的威力。
  • k1表示属性一致加成，当招式的属性和宝可梦的其中一个属性相同时，，否则k1 = 1
  • k2表示属性相克加成。宝可梦世界中一共有18种属性：一般（Normal）、飞行（Flying）、火（Fire）、超能力（Psychic）、水（Water）、虫（Bug）、电（Electric）、岩石（Rock）、草（Grass）、幽灵（Ghost）、冰（Ice）、龙（Dragon）、格斗（Fighting）、恶（Dark）、毒（Poison）、钢（Steel）、地面（Ground）、妖精（Fairy）。下表每一行表示某属性的招式对各个属性的宝可梦的属性相克加成，例如使用火属性的招式攻击水属性的宝可梦时，。对于具有两个属性的宝可梦，分别计算属性相克加成然后相乘，例如使用冰属性的招式攻击飞行+龙属性的宝可梦时，k2 = 2 × 2 = 4。一个特殊规则是，如果k2 = 0，那么伤害将直接为0，而不会按照上面的公式计算。
     一般格斗飞行毒地面岩石虫幽灵钢火水草电超能力冰龙恶妖精
    一般1×1×1×1×1×1⁄2×1×0×1⁄2×1×1×1×1×1×1×1×1×1×
    格斗2×1×1⁄2×1⁄2×1×2×1⁄2×0×2×1×1×1×1×1⁄2×2×1×2×1⁄2×
    飞行1×2×1×1×1×1⁄2×2×1×1⁄2×1×1×2×1⁄2×1×1×1×1×1×
    毒1×1×1×1⁄2×1⁄2×1⁄2×1×1⁄2×0×1×1×2×1×1×1×1×1×2×
    地面1×1×0×2×1×2×1⁄2×1×2×2×1×1⁄2×2×1×1×1×1×1×
    岩石1×1⁄2×2×1×1⁄2×1×2×1×1⁄2×2×1×1×1×1×2×1×1×1×
    虫1×1⁄2×1⁄2×1⁄2×1×1×1×1⁄2×1⁄2×1⁄2×1×2×1×2×1×1×2×1⁄2×
    幽灵0×1×1×1×1×1×1×2×1×1×1×1×1×2×1×1×1⁄2×1×
    钢1×1×1×1×1×2×1×1×1⁄2×1⁄2×1⁄2×1×1⁄2×1×2×1×1×2×
    火1×1×1×1×1×1⁄2×2×1×2×1⁄2×1⁄2×2×1×1×2×1⁄2×1×1×
    水1×1×1×1×2×2×1×1×1×2×1⁄2×1⁄2×1×1×1×1⁄2×1×1×
    草1×1×1⁄2×1⁄2×2×2×1⁄2×1×1⁄2×1⁄2×2×1⁄2×1×1×1×1⁄2×1×1×
    电1×1×2×1×0×1×1×1×1×1×2×1⁄2×1⁄2×1×1×1⁄2×1×1×
    超能力1×2×1×2×1×1×1×1×1⁄2×1×1×1×1×1⁄2×1×1×0×1×
    冰1×1×2×1×2×1×1×1×1⁄2×1⁄2×1⁄2×2×1×1×1⁄2×2×1×1×
    龙1×1×1×1×1×1×1×1×1⁄2×1×1×1×1×1×1×2×1×0×
    恶1×1⁄2×1×1×1×1×1×2×1×1×1×1×1×2×1×1×1⁄2×1⁄2×
    妖精1×2×1×1⁄2×1×1×1×1×1⁄2×1⁄2×1×1×1×1×1×2×2×1×
  • 表示17到20之间的随机整数（包含边界）。
  • 注意最后的结果要向下取整，但至少为1。

Pecco和Index的对战地点选在白银山，这里终年下冰雹，每个回合结束后（双方轮流打出一个招式后），双方都会受到伤害：，其中hp表示该宝可梦的初始HP。为了简化题目，我们假设冰属性的宝可梦也会受到伤害，这与游戏的设定不同。

直到一方HP减少到0或更低，则该方落败。如果两方同时倒下，认为速度较快的一方落败。

假设Pecco和Index都很聪明，每回合都会令他们的宝可梦打出使自己获胜概率最高的招式。试求出 Pecco的胜率。

Input

整个输入文件共12行，前6行为Pecco的宝可梦的描述，后6行为Index的宝可梦的描述。

每个宝可梦的描述的第一行包含6个正整数（ ≤ 500），表示它的HP、物攻，物防，特攻，特防和速度。

接下来一行包含一个整数n（），表示该宝可梦属性的数量。然后是n个属性字符串，表示该宝可梦的属性。

接下来四行分别描述该宝可梦的四个技能。每行包含两个正整数p和h（p ≤ 300, h ≤ 100），表示威力是p、命中率是。然后是一个属性字符串t。再然后是一个字符串Physical或Special，Physical表示这是物理招式，Special表示这是特殊招式。

属性字符串的取值包括："Normal", "Fire", "Fighting", "Water", "Flying", "Grass", "Poison", "Electric", "Ground", "Psychic", "Rock", "Ice", "Bug", "Dragon", "Ghost", "Dark", "Steel", "Fairy"。

Output

输出一行一个实数，表示Pecco的胜率。如果你的答案与评测机的答案的绝对误差在10 - 4之内，则会被认为是正确的。

Examples
Input
145 90 135 150 110 80
2 Electric Steel
110 70 Electric Special
90 100 Electric Special
80 100 Steel Special
150 90 Normal Physical
143 85 85 145 135 100
2 Psychic Fairy
80 100 Fairy Special
90 100 Psychic Special
80 100 Ghost Special
85 100 Normal Physical
Output
1.000000
Input
1 100 100 100 100 105
1 Dragon
250 90 Normal Special
240 100 Normal Special
40 100 Normal Special
40 100 Normal Physical
112 100 100 100 100 100
1 Dragon
100 100 Normal Special
100 100 Ice Special
100 100 Fairy Special
100 100 Dragon Special
Output
0.225000

H. 玻璃球
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小M将 N 个不同的玻璃球放置在恰好 N 个不同的平台上，有 N - 1 条管道连接这些球（可以抽象为一棵 N 个节点的树），你可以认为这个管道系统是自叶子向至根（1号节点）的，即子节点一定在父节点的上方。

这些球是不安定的，由于小M非常的粗心，不小心触碰了系统，因此这些球都讲沿着管道自然下落，每个球通过一个管道需要花费一个单位的时间。然而，由于玻璃球极易破碎，因此如果他们触碰到了彼此，将会破碎。 小M可以在任意的平台上放置回收装置，从而回收落入该平台的玻璃球；否则，如果玻璃球没有被回收装置回收，将会沿着管道继续下落。

然而，由于这些装置是最新研发的，因此有一定概率会无法工作，在第 i 个平台的回收装置成功工作的概率为 pi。

小M想要知道期望所有被回收的玻璃球将会经过的管道数之和对 998 244 353 取模后的结果。

Input

输入的第一行是一个正整数 N( ≤ N ≤ 5 × 105)。

第二行包含 N 个被空格分隔的非负整数 pi( < 998 244 353)，保证 p1 ≡ 1，在模 998 244 353 的意义下给出。

第三行包含 N - 1 个被空格分隔的正整数 fi + 1，第 i 个整数表示第 i + 1 个平台有一个向下连接到第 fi + 1 平台的管道。

Output

输出一行一个整数表示答案。

Examples
Input
3
1 499122177 499122177
1 1
Output
499122177
Input
4
1 499122177 665496236 665496236
1 2 2
Output
166374060
Note

对于分数 ，其对 998 244 353 取模的结果是 P·Q - 1 ± od{998244353}，其中 Q·Q - 1 ≡ 1 ± od{998244353}。

对于样例1，pi 分别为 , 当第二个平台与第三个平台上的装置仅有一个工作时, 答案为 1 + 0 + 0 = 1, 否则答案为 0，因此最终答案为 .

对于样例2，pi 分别为 , 当第二个平台上的装置工作且第三、四平台上的装置仅有一个工作时，答案为 1, 否则答案 0; 当第二个平台上的装置不工作且第三、四平台上的装置仅有一个工作时, 答案为 2 + 1 = 3, 否则答案为 1, 因此最终答案为 .

I. 期中考试
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

由于最近打的比赛 CPCX-岛皇秦站打铁了，小 Z 正在加训！在接下来若干个星期 $$$x_0$$$、星期 $$$x_1$$$、星期 $$$x_2$$$，小 Z 将加训！

但在第 $$$a_0$$$ 周的星期 $$$a_1$$$ 早上 $$$00:00$$$，小 Z 突然发现第 $$$b_0$$$ 周的星期 $$$b_1$$$ 将会进行若干场期中考试。小 Z 想知道，除去要加训的那些天，小 Z 还能复习多少天？

假设第 $$$a_0$$$ 周的星期 $$$a_1$$$ 当天小 Z 还能进行自由活动（加训或者复习），而考试当天只能进行考试。

Input

第一行包含用空格分隔的三个正整数 $$$x_0, x_1, x_2(1\le x_0 \lt x_1 \lt x_2 \le 7)$$$ 表示每一周加训的那些天；

第二行包含用空格分隔的四个正整数 $$$a_0, a_1, b_0, b_1(1\le b_0, b_1 \le 7)$$$ 分别表示小 Z 当前的日期和考试的日期，保证 $$$1\le a_0 \le b_0 \le 1\ 000$$$ 且当 $$$a_0 = b_0$$$ 时 $$$a_1 \lt b_1$$$。

Output

输出一行一个整数，表示小 Z 还能进行复习的天数。

Example
Input
2 3 4
1 1 10 7
Output
39

J. 进制转换
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 Z 刚刚学习了二进制！二进制数是用 $$$0$$$ 和 $$$1$$$ 两个数码来表示的数。它的基数为 $$$2$$$，进位规则是"逢二进一"，借位规则是"借一当二"。对于一个长度为 $$$m$$$ 的二进制串，其可以表示 $$$[0\sim 2^m)$$$ 的值。聪慧的小 Z 很快引申到了 $$$n$$$ 进制数，她意识到，对于任意大于 $$$1$$$ 的正整数 $$$n$$$，一个长度为 $$$m$$$ 的 $$$n$$$ 进制数可以表示所有 $$$[0\sim n^m)$$$ 的值。但小 Z 并不满足于正整数，她还想知道某种特殊定义下的 $$$a/b$$$ 进制下的情况......

小 Z 的问题形式化地表示如下，给出一个正数 $$$n$$$ （其中 $$$n$$$ 以 $$$x = n \times b^m$$$ 的形式给出，$$$x$$$ 是一个不超过 $$$10^{18}$$$ 的正整数）、正整数 $$$m,a,b$$$ 和一个长度为 $$$m+1$$$ 的序列 $$$c_i$$$（下标从 $$$0$$$ 开始），问是否能选出一个长度为 $$$k$$$ 的非空整数序列 $$$s$$$，满足 $$$0\le s_1 \lt s_2 \lt \cdots \lt s_k \le m$$$，使得 $$$n = \sum_{i=1}^k c_{s_i} \times (\frac{a}{b})^{s_i}$$$。在有解的情况下，小 Z 还希望这个序列的长度 $$$k$$$ 尽量小，并想知道在满足 $$$k$$$ 最小情况下的方案数，以及其中任意一种方案。若无解的话，只要告诉小 Z 一行一个 $$$-1$$$ 表示无解即可。

小 Z 觉得 $$$a=b$$$ 非常的简单，所以她保证了 $$$a \ne b$$$；但是她又觉得这道题非常的困难，所以她又保证了对于任意 $$$c_i$$$，$$$c_i$$$ 与 $$$a$$$、$$$b$$$ 同时互质。小 Z 认为大部分选手会使用 C++ 作答，所以她还贴心的保证了对于任意 $$$i (0\le i\le m)，c_i \times a_i^i \cdot b_i^{m-i} \le 10^{18}$$$。

Input

本题有多组测试数据。

输入的第一行为一个正整数 $$$T$$$（$$$1\le T\le 50000$$$），表示数据组数。每组数据共有两行输入。

每组数据的第一行包含四个用空格分隔正整数 $$$x,m,a,b$$$（$$$1\le x,a,b \le 10^{18}$$$；$$$1\le m\le 60$$$；$$$a\ne b$$$），含义如上文所述；

第二行包含 $$$m+1$$$ 个用空格分隔正整数 $$$c_0, c_1, \cdots , c_m$$$，含义如上文所述。

Output

对于每组数据，若不存在这样的序列 $$$s$$$，则输出一行一个 $$$-1$$$；

若有解，则第一行输出两个用空格分隔的整数 $$$k$$$ 和 $$$num$$$，分别表示使序列 $$$s$$$ 长度最短的长度 $$$k$$$ 和方案数 $$$num$$$；第二行输出一个长度为 $$$m+1$$$ 的 $$$01$$$ 串，表示其中一种合法方案，其中第 $$$i$$$ 个数为 $$$1$$$ 则表示数字 $$$i - 1$$$ 在序列 $$$s$$$ 中；若为 $$$0$$$ 则表示不在。

若有多种合法方案，输出其中任意一种即可。

Example
Input
3
104 3 2 4
1 1 3 3
130 1 65 143
1 2
97 3 4 6
1 1 1 1
Output
3 1
0111
1 1
01
-1

K. 方格填数
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

小 Z 正在研究方格！现在在小 Z 面前有个 n × m 的方格图，其中每个方格上都有一个 的正整数。

小 Z 对于最大值很感兴趣，因此，她会留意这个方格图中的"极大方格"。对于某个方格，他是极大方格当且仅当这个方格中的数字严格大于与该方格同行或是同列的其他方格的数字。

现在这个方格图所有方格都是空的，定义 f(i) 为使方格图的"极大方格"数不少于 i 的填数方案。小 Z 想要知道， 的值？

由于这个结果可能很大，小 Z 只要求你求出答案对于109 + 7取模的结果即可。

Input

输入一行共三个整数 n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ 1018)，含义如上文所述。

Output

输出一行共一个整数，表示答案的值对109 + 7取模的结果。

Examples
Input
1 2 3
Output
15
Input
11 45 14
Output
181394144
Input
114514 1919 810
Output
710129823
Note

对于第一个样例，一共有 {1, 1}、{1, 2}、{1, 3}、{2, 1}、{2, 2}、{2, 3}、{3, 1}、{3, 2}、{3, 3} 共 9 种填数方案，其中"极大方格"数分别为 0、1、1、1、0、1、1、1、0。f(0) = 9，f(1) = 6，其余 f(x) 值均为 0，因此答案为 15。

L. 兄弟校问题
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

我们称两个学校如果处于同一个城市或者两个学校的校名中有相同的关键词就是兄弟学校；

如果两个学校同时是某一个学校的兄弟学校，那么这两个学校也是兄弟学校；

给定关键词列表和每个学校的校名和城市，求每个学校的兄弟学校的个数。

一个学校的校名中有关键词，指的是其校名中完整的单词在关键词列表中完全一致地出现。

Input

第一行是两个整数n, m分别表示学校数量和关键词数量。 接下来n(1 ≤ n ≤ 1 000)行，每行两个用空格分隔的只包含大小写字母和分隔符"_"的字符串（长度不超过1 000)，分别表示学校名称和城市名称，其中学校名称的不同单词之间的分隔符用下划线"_"代替空格，关键词大小写不敏感，城市名称不包含分隔符。 接下来m(0 ≤ m ≤ 1 000)行，每行一个只包含小写字母的字符串（长度不超过5 0)，描述关键词列表。

Output

输出n行，每行一个整数，描述第i个学校的兄弟学校个数。

Examples
Input
4 1
jimei_University Xiamen
xiamen_University Xiamen
genshin_University Mihoyo
genshin_Impact Mihoyo
genshin
Output
1
1
1
1
Input
2 0
genshin_Impact Mihoyo
star_Railway_University Mihuyou
Output
0
0