問題文
吉雄是个以天体观测为爱好的好人。
今晚也像往常一样,他开始在窗外看到的夜空中,寻找自己想象的星座并开始数数的游戏。
吉雄从夜空中的星星中选出一些星,如果这些星的相对位置与特定星座完全一致,就认为那个星座出现了一次。
如果有多个组合的星会形成同一个星座,则全部计为该星座的一次出现。
另外,不会对星座进行翻转、旋转或缩放。
例如,考虑夜空中的星星具有以下位置关系的情况。(o为有星的位置,.为空格)
o.. .o. ..o
在这片夜空中,
o
这个星座出现了3次。
o. .o
这个星座出现了2次。此时,夜空中央的星星被使用了2次。
o.. ... ..o
这个星座出现了1次。夜空中不属于任何星座的中央星星被忽略。
o... .... .... ...o
这个星座没有出现。
已知夜空中星星的排列和星座,请编写程序计算每个星座在夜空中出现的次数。
入力
输入是按以下格式从标准输入给出的。
N M X1 Y1 : XN YN L1 SX1,1 SY1,1 : SX1,L1 SY1,L1 : LM SXM,1 SYM,1 : SXM,LM SYM,LM
- 1 行表示夜空中星星的数量 N (1 \leq N \leq 105) 以及想要查找的星座数量 M (1 \leq M \leq 100) 。 表示
- 2 从行 N 行是、i 第n颗夜空中星星的位置坐标 Xi(0 \leq Xi \leq 106) 和 按字典顺序比较 Yi(0 \leq Yi \leq 106) 。 表示
- p \neq q 然后,Xp \neq Xq 或 至少 Yp \neq Yq 很满意。
- N+2 从下一行开始,以下内容重复 M 指定次数。
- j 第n个星座包含的星星数量 Lj (1 \leq Lj \leq 100) 。 表示
- 继续 Lj 行是、j 第n个星座的 k 第m颗星的位置坐标 SXj,k(0 \leq SXj,k \leq 9) 和 按字典顺序比较 SYj,k(0 \leq SYj,k \leq 9) 。 表示
- p \neq q 然后,SXj,p \neq SXj,q 或 至少 SYj,p \neq SYj,q 很满意。
部分点
- N \leq 100在所有情况都答对时,作为部分分数给予 40 分。
出力
统计夜空中各个星座出现的次数 1 按行进行总计 M 行。在输出末尾添加换行符。
入力例1
3 4 1 1 2 2 3 3 1 0 0 2 0 0 1 1 2 0 0 2 2 2 0 0 3 3
出力例1
3 2 1 0
这与题目中给出的例子相同,从上到下分别为3、2、1、0。
入力例2
11 4 21 11 21 12 21 13 21 14 22 11 23 11 24 11 22 13 23 12 23 13 24 13 3 1 1 2 1 1 2 3 1 1 1 2 2 2 3 3 2 2 3 3 3 3 3 3 4 3 4 4
出力例2
3 2 1 1
给定的夜空中的星星位置关系如下。
oooo o.o. oooo o...
针对这些星星所给出的星座是:
oo o.
o. oo
.o oo
oo .o
这种排列,所以从上到下分别为3、2、1、1。