Bajtek and Bitek love watching trains passing near their house. They have a particular passion for freight trains, as they are usually very long and have a variety of wagons. The boys decided to document the types of wagons the trains consist of. For simplicity, we will number the potential types of wagons from $1$ to $k$. Wagons of the same type are indistinguishable to the boys.
When a train passes, both boys write down the types of consecutive wagons in their notebooks. Bajtek is older and can already write down the types of all wagons without any mistakes. Bitek is younger and does not have as much writing practice yet. It sometimes happens that before he manages to write down the type of a wagon, several subsequent wagons pass through the crossing, which Bitek does not notice. Thus, some of the wagons may be omitted from Bitek's list.
The boys are now analyzing their notes and wondering which of the train's wagons Bitek could have written down, and which were definitely missed by him.
Input
The first line of input contains three integers $n$, $m$, and $k$ ($1 \le n, m, k \le 300\,000$), denoting respectively the length of Bajtek's list (equal to the number of wagons in the train), the length of Bitek's list, and the number of different wagon types.
The second line contains a sequence of $n$ integers from the interval $[1, k]$, representing the consecutive wagon types on Bajtek's list.
The third line contains a sequence of $m$ integers in the same format — Bitek's list.
You can assume that Bitek might have omitted some wagons from Bajtek's list, but did not write down anything "extra". In other words, the input data is chosen such that it is possible to delete some number of wagons (possibly zero) from Bajtek's list to obtain Bitek's list.
Output
The output should contain $n$ integers separated by single spaces: the $i$-th of these numbers should be $1$ if the $i$-th wagon could have been written down by Bitek, or $0$ if it definitely could not have been written down.
Examples
Input 1
9 4 3 1 3 2 1 2 3 1 3 2 1 3 1 2
Output 1
1 1 0 1 1 1 1 0 1
Note
Bitek could have written down the wagons with the following indices (1-based):
- 1, 2, 4, and 5,
- 1, 2, 4, and 9,
- 1, 2, 7, and 9,
- 1, 6, 7, and 9,
- or 4, 6, 7, and 9.
Grading
The test set is divided into the following subtasks.
| Subtask | Constraints | Time Limit | Points |
|---|---|---|---|
| 1 | $n, m \le 100$ | 1 s | 15 |
| 2 | $n, m \le 2000$ | 10 s | 20 |
| 3 | Each wagon type appears in the train at most once | 6 s | 15 |
| 4 | No additional constraints | 6 s | 50 |
Evaluation Tests
The following public evaluation tests are available:
- 1ocen: $n = 10$, $m = 1$, $k = 1$ (wagons of a single type); the output consists entirely of ones.
- 2ocen: $n = 4M + 3$, $m = 2M + 1$, $k = 2$ (for $M = 24\,999$); Bajtek's sequence is $(1\ 2)^M\ 1\ 2\ 1\ (2\ 1)^M$, Bitek's sequence is $1^M\ 2\ 1^M$; the output is the sequence $(1\ 0)^{M-1}\ 1^7\ (0\ 1)^{M-1}$.