Background

This problem is translated from POI2022~2023R1 poc.

Problem Description

Little A and Little B are recording the types of vehicles that passed by.

There are $1 \sim k$ types in total, and every vehicle must belong to exactly one of them.

Little A carefully recorded the types of all vehicles in order, while playful Little B only recorded some of the vehicles in order.

The length of Little A’s record is $n$, and the length of Little B’s record is $m$.

We say that the $i$-th vehicle in Little A’s record “may have been recorded by B” if and only if there exists a subsequence of Little A’s record that contains position $i$ and is exactly the same as the sequence recorded by Little B.

It is guaranteed that Little B’s sequence is a subsequence of Little A’s sequence. Determine which vehicles may have been recorded by Little B and which may not.

Input Format

The first line contains three integers $n, m, k \ (1 \leq n, m, k \leq 3 \times 10^5)$.

The second line contains a sequence of length $n$, representing the sequence recorded by Little A.

The third line contains a sequence of length $m$, representing the sequence recorded by Little B.

All elements in the sequences satisfy $1 \leq$ sequence element $\leq k$.

Output Format

For each vehicle recorded by Little A, determine whether it can be recorded by Little B. Output $1$ if it can, and $0$ otherwise.

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

Hint

For the sample, the following subsequences exist:

$(1,2,4,5)$, $(1,2,4,9)$, $(1,2,7,9)$, $(1,6,7,9)$, $(4,6,7,9)$.

Note that $3$ and $8$ are never chosen, so they cannot be recorded by Little B.

The subtasks are as follows:

Time limit: Subtask 1 1s, Subtask 2 10s, Subtask 3 and Subtask 4 6s.

Translated by ChatGPT 5