题目内容

在大语言模型处理输入文本时，为了防止敏感数据被意外记忆或泄露，安全框架会先对输入序列进行预扫描，并与预设的敏感词库进行匹配。一旦匹配到敏感内容，系统会在底层的注意力掩码矩阵中对相应区块进行动态隔离遮蔽。敏感区块内部的词元可以互相访问，但区块外部的任何位置都不能读取这些敏感信息。

给定一个长度为 $N$ 的主序列 $T$，其中每个元素是一个 Token ID。再给定 $K$ 个敏感模式串，每个模式串也是 Token ID 序列。

首先进行模式匹配与敏感区块合并。对于每个敏感模式串，在主序列 $T$ 中找出它每一次出现的首尾下标，形成一个闭区间 $[L, R]$。若两个区间相交，即交集非空；或首尾相邻，即一个区间的左端点等于另一个区间右端点加 1（例如 $L_b = R_a + 1$ 或 $L_a = R_b + 1$），则需要将它们合并。合并后得到的若干互不相交且互不首尾相邻的连续区间称为敏感块。

然后依据动态遮蔽规则计算可见性。对于序列中的任意位置 $i$ 和目标位置 $j$（满足 $0 \le j \le i < N$），$i$ 能否观察到 $j$ 由以下规则确定：

• 如果 $j$ 属于某个敏感块，那么只有当 $i$ 也位于同一个敏感块内部时，$i$ 才能观察到 $j$。
• 如果 $j$ 不属于任何敏感块，那么所有满足 $j \le i$ 的后续位置都能正常观察到 $j$。

你需要计算每个位置 $i$ 在整个序列中总共能观察到的位置数量。

约束条件：

主序列长度 $N$ 满足 $1$ ≤ $N$ ≤ $10^5$；

敏感模式串数量 $K$ 满足 $1$ ≤ $K$ ≤ $100$；

每个敏感模式串长度 $M$ 满足 $1$ ≤ $M$ ≤ $1000$。

输入描述

第一行包含两个整数 $N$ 和 $K$，以空格分隔，分别表示主序列长度和敏感模式串数量。

第二行包含 $N$ 个整数，以空格分隔，表示主序列 $T$ 的 Token ID。

接下来 $K$ 行，每行描述一个敏感模式串：第一个整数 $M$ 表示该模式串长度，随后 $M$ 个整数以空格分隔，表示该敏感模式串的 Token ID 序列。

输出描述

输出一行，包含 $N$ 个整数，以空格分隔，依次表示从下标 0 到 $N-1$ 每个位置 Token 在整个序列中可观察到的 Token 数量。

样例1

输入

1 1
7
1 7

输出

1

说明

主序列只有 1 个 Token，下标为 0。敏感模式串 [7] 在主序列中出现一次，对应区间为 $[0,0]$，因此敏感块就是 $[0,0]$。

位置 0 位于该敏感块内，所以它能观察到同一敏感块中不超过 0 的位置，也就是它自身，可见数量为 1。

样例2

输入

5 1
1 2 1 2 3
2 1 2

输出

1 2 3 4 1

说明

敏感模式串 [1,2] 在主序列中出现两次，出现区间分别是 $[0,1]$ 和 $[2,3]$。由于 $2 = 1 + 1$，两个区间首尾相邻，合并后得到敏感块 $[0,3]$。

在敏感块内部，可见数量等于进入块前的普通 Token 数加上块内已扫描的 Token 数。

位置 0 到 3 均在敏感块内：

• 位置 0 可见 1 个；
• 位置 1 可见 2 个；
• 位置 2 可见 3 个；
• 位置 3 可见 4 个。

位置 4 不属于任何敏感块，此前普通 Token 数为 0，它自身是普通 Token，所以可见 1 个。

最终输出为 1 2 3 4 1。

样例3

输入

8 2
5 1 2 3 9 2 3 4
3 1 2 3
3 2 3 4

输出

1 2 3 4 2 3 4 5

说明

敏感模式串 [1,2,3] 出现在区间 $[1,3]$；敏感模式串 [2,3,4] 出现在区间 $[5,7]$。两个区间之间还有普通位置 4，因此它们不相交也不首尾相邻，不需要合并，形成两个敏感块 $[1,3]$ 和 $[5,7]$。

位置 0 是普通 Token，可见数量为 1。

在第一个敏感块 $[1,3]$ 中：

• 进入该块前已有普通 Token 数量为 1，即位置 0。
• 位置 1 可见 $1 + 1 = 2$ 个；
• 位置 2 可见 $1 + 2 = 3$ 个；
• 位置 3 可见 $1 + 3 = 4$ 个。

位置 4 是普通 Token，此时普通 Token 累计为 2，可见数量为 2。

在第二个敏感块 $[5,7]$ 中：

• 进入该块前已有普通 Token 数量为 2，即位置 0 和位置 4。
• 位置 5 可见 $2 + 1 = 3$ 个；
• 位置 6 可见 $2 + 2 = 4$ 个；
• 位置 7 可见 $2 + 3 = 5$ 个。

最终输出为 1 2 3 4 2 3 4 5。

样例4

输入

3 1
1 2 3
1 9

输出

1 2 3

说明

敏感模式串 [9] 没有在主序列中出现，因此没有任何敏感块，全部位置都是普通 Token。

对于普通 Token，每个位置 $i$ 能观察到所有满足 $j \le i$ 且不属于敏感块的位置。由于所有位置都不属于敏感块：

• 位置 0 可观察 1 个；
• 位置 1 可观察 2 个；
• 位置 2 可观察 3 个。

最终输出为 1 2 3。