题目内容

在一个由 N 个节点组成的 LLM 推理集群中，需要实现一个请求路由器。每个节点维护自己的 KV Cache，其中保存了已经完成 prefill 的请求的完整 token 序列。节点负载定义为该节点当前还没有处理完的 token 总量。

当一条新请求到来时，如果它的起始 token 片段与某个节点缓存中某条序列的起始片段完全相同，那么这个片段在 prefill 阶段可以直接复用，不必重新计算。复用的 token 数越多，节省的 prefill 计算量越大，也越能降低 TTFT（Time To First Token）。

对于两个 token 序列，它们的最长公共前缀 LCP 是满足 0 ≤ k ≤ min(len(a), len(b)) 且对任意 0 ≤ j < k 都有 a[j] = b[j] 的最大整数 k。

对于一个节点，定义它关于当前请求的可复用前缀长度为：该节点缓存中所有序列与当前请求的 LCP 长度的最大值。

路由时按以下优先级决定：

1. 选择可复用前缀长度最大的节点，即与当前请求拥有最长公共前缀的节点。
2. 若有多个节点的最大可复用前缀长度相同（包括所有节点均为 0 的情况），选择当前负载最小的节点。

每次路由完成后，必须立即更新状态：

• 将当前请求的完整 token 序列加入所选节点的 KV Cache。
• 将当前请求的 token 数量 $len(request)$ 累加到所选节点的负载上。

后续请求进行路由时，必须基于更新后的缓存和负载状态。

输入描述

第一行包含两个整数 N 和 M，用空格分隔，分别表示节点数量和请求数量。

第二行包含 N 个整数，用空格分隔，依次为 load[0] 到 load[N-1]，表示每个节点的初始负载。

接下来 N 行，每行描述一个节点的初始 KV Cache。行首是一个整数 K，表示该节点缓存的序列条数。如果 K 为 0，则该行只有一个 0。如果 K 大于 0，则行首 K 之后还有 K 个字符串，每个字符串表示一条缓存序列；字符串内是用逗号分隔的 token 列表，只含一个 token 时没有逗号。

再接下来 M 行，每行描述一个请求。每行包含用空格分隔的整数，依次为该请求的 token 序列。

输出描述

输出一行，包含 M 个整数，用空格分隔。其中第 i 个整数表示第 i 个请求被分配到的节点编号，节点编号从 0 开始。

样例1

输入

2 3
5 3
2 1,2,3 4,5
1 1,2,4
1 2 3
1 2 5
4 5

输出

0 1 0

说明

初始负载：节点 0 为 5，节点 1 为 3。

节点 0 缓存序列为 [1,2,3] 和 [4,5]，节点 1 缓存序列为 [1,2,4]。

请求 [1,2,3] 与节点 0 的 [1,2,3] 完全匹配，LCP 长度为 3；与节点 1 的 [1,2,4] 的 LCP 为 [1,2]，长度为 2。因此选择节点 0，随后节点 0 负载增加 3，变为 8。

请求 [1,2,5] 与节点 0 的 [1,2,3] 以及节点 1 的 [1,2,4] 的 LCP 均为 [1,2]，长度均为 2。两者最大可复用前缀长度相同，比较负载：节点 0 当前负载为 8，节点 1 为 3，因此选择节点 1。节点 1 负载增加 3，变为 6。

请求 [4,5] 与节点 0 的 [4,5] 完全匹配，LCP 长度为 2，而节点 1 没有可匹配前缀，LCP 为 0，所以选择节点 0。节点 0 负载增加 2，变为 10。

最终输出 0 1 0。

样例2

输入

3 2
10 5 7
0
1 100
1 200
1 2 3
100 101

输出

1 1

说明

初始负载：节点 0 为 10，节点 1 为 5，节点 2 为 7。

节点 0 缓存为空，节点 1 缓存有 [100]，节点 2 缓存有 [200]。

请求 [1,2,3] 与三个节点的缓存都没有公共前缀，LCP 均为 0。在所有节点最大可复用前缀长度相同的情况下，选择当前负载最小的节点，即负载为 5 的节点 1。随后节点 1 负载增加 3，变为 8，并将该请求序列加入缓存。

请求 [100,101] 与节点 1 缓存中的 [100] 有公共前缀 [100]，LCP 长度为 1；与节点 2 的 [200] 和节点 0 的空缓存 LCP 均为 0。因此选择节点 1，节点 1 负载增加 2，变为 10。

最终输出 1 1。

样例3

输入

1 1
0
0
42

输出

0

说明

只有一个节点 0，初始负载为 0，缓存为空。

请求 [42] 无法复用任何已有前缀，但由于它是唯一可选节点，因此分配给节点 0，节点 0 负载增加 1，变为 1。

最终输出 0。