题目背景

题目译自 POI2022~2023R1 poc。

题目描述

小 A 和小 B 在记录过往的车辆的类型！

已知类型分别有 $1 \sim k$ 个，每种车辆必然属于其中之一。

小 A 按顺序细心地记录了所有的车辆的类型，但是贪玩的小 B 只按顺序记录了一部分车辆。

小 A 记录的内容长度为 $n$，小 B 记录的长度为 $m$。

称在小 A 记录中的第 $i$ 辆车“可能被 B 记录到”当且仅当在小 A 的记录中存在一个包含 $i$ 的子序列与小 B 所记录的完全相同。

保证小 B 记录的序列一定是小 A 记录的子序列，问哪些车辆是可能会被小 B 记录到，哪些没有。

输入格式

第一行三个整数 $n,m,k \ (1 \leq n,m,k \leq 3 \times 10^5)$。

第二行一个长度为 $n$ 的序列，表示小 A 记录的序列。

第三行一个长度为 $m$ 的序列，表示小 B 记录的序列。

上述序列中的元素均满足 $1\leq$ 序列元素 $\leq k$。

输出格式

对于每个小 A 记录到的车辆，请确定它能否被记录到，能输出 $1$，不能输出 $0$。

9 4 3
1 3 2 1 2 3 1 3 2
1 3 1 2

1 1 0 1 1 1 1 0 1

提示

对于样例，存在如下的子序列：

$(1,2,4,5)$，$(1,2,4,9)$，$(1,2,7,9)$，$(1,6,7,9)$，$(4,6,7,9)$。

注意到 $3$ 和 $8$ 一直都没被取到，故不能被小 B 记录到。

子任务分配如下：

时间限制：Subtask1 1s，Subtask2 10s，Subtask3 和 Subtask4 6s。