#CPP1I. 分片复原

分片复原

题意:

有 mm 条消息。第 ii 条消息原本由 kik_i 个非空片段依次拼接而成,片段位置从 11 到 kik_i 编号。

现在收到 nn 条片段记录,每条记录给出消息编号、片段位置和片段内容。记录可能乱序、重复,也可能缺失。

请对每条消息按以下优先级输出结果:

  1. 如果同一片段位置收到过不同内容,输出 CONFLICT。即使还存在缺失片段,也优先输出这个结果。
  2. 否则,如果至少一个片段位置没有收到记录,输出 INCOMPLETE。
  3. 否则,输出 OK 和完整消息,中间以一个空格分隔。完整消息按照片段位置从小到大直接拼接,不添加分隔符。

同一位置重复收到完全相同的内容不算冲突,并且该片段只拼接一次。不同位置允许具有相同内容。

输入格式:

第一行两个整数 mm、nn(1≤m≤1051 \le m \le 10^5,0≤n≤2×1050 \le n \le 2\times10^5),分别表示消息数量和收到的记录数量。

第二行 mm 个整数 k1,k2,…,kmk_1,k_2,\ldots,k_m(1≤ki≤2×1051 \le k_i \le 2\times10^5),表示各条消息的片段数。保证 ∑i=1mki≤2×105\sum_{i=1}^m k_i \le 2\times10^5。

接下来 nn 行,每行给出两个整数 uu、pp 和一个字符串 ss(1≤u≤m1 \le u \le m,1≤p≤ku1 \le p \le k_u,1≤∣s∣≤201 \le |s| \le 20),分别表示消息编号、片段位置和片段内容。字符串仅由小写英文字母组成。

输出格式:

输出 mm 行,第 ii 行为第 ii 条消息的结果,格式为 CONFLICT、INCOMPLETE 或 OK content,其中 content 替换为完整消息。

样例:

样例输入1:

4 8
3 2 2 1
1 2 cd
1 1 ab
1 2 cd
1 3 e
2 1 x
2 1 y
3 2 zz
4 1 hi

样例输出1:

OK abcde
CONFLICT
INCOMPLETE
OK hi

样例解释1:

第 11 条消息的第二个片段重复出现,但内容相同。第 22 条消息的第一个片段存在冲突,因此即使第二个片段缺失,也输出 CONFLICT。

样例输入2:

1 0
1

样例输出2:

INCOMPLETE