John and Alex like to watch cars passing by on the street. When the car drives past, both boys write down the types of cars in their notebooks. John is older and can write down all the cars flawlessly. Alex is younger and may not notice some cars. So, in Alex's list, some cars may be left out. The boys analyze their records and ponder which cars Alex might have noted and which he sure couldn't.
Input: The first line of input contains three integers n, m and k (1 ≤ n, m, k ≤ 300,000), denoting successively the length of the John list (equal to the number of cars), the length of the Alex's list, and the number of different types of cars. In the second line there is a sequence of length n composed of integers from the interval [1, k], denoting more types of cars on John's list. In the third line there is a sequence of length m in the same format - Alex's list. You can assume that Alex may have omitted some of the cars from John's list, but didn't add anything "extra". In other words, the input data is chosen such that it is possible to erase a certain number of cars (possibly zero) from the list John and get Alex's list.
Output: The output should contain n integers separated by single spaces: the i-th of these numbers shall be equal to 1 if the i-th car could have been noted by Alex, or 0 if it certainly could not be noted down
Example1:
12 6 6
6 1 1 3 3 6 2 5 4 1 1 3
6 1 1 3 2 5
1 1 1 1 1 0 1 1 0 0 0 0 # Answer/Output
Example2:
16 9 4
1 1 1 4 3 1 1 2 4 1 1 2 2 1 3 1
1 1 1 4 1 2 2 1 3
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 # Answer/Output
Can you help me write code for that problem?
Input: The first line of input contains three integers n, m and k (1 ≤ n, m, k ≤ 300,000), denoting successively the length of the John list (equal to the number of cars), the length of the Alex's list, and the number of different types of cars. In the second line there is a sequence of length n composed of integers from the interval [1, k], denoting more types of cars on John's list. In the third line there is a sequence of length m in the same format - Alex's list. You can assume that Alex may have omitted some of the cars from John's list, but didn't add anything "extra". In other words, the input data is chosen such that it is possible to erase a certain number of cars (possibly zero) from the list John and get Alex's list.
Output: The output should contain n integers separated by single spaces: the i-th of these numbers shall be equal to 1 if the i-th car could have been noted by Alex, or 0 if it certainly could not be noted down
Example1:
12 6 6
6 1 1 3 3 6 2 5 4 1 1 3
6 1 1 3 2 5
1 1 1 1 1 0 1 1 0 0 0 0 # Answer/Output
Example2:
16 9 4
1 1 1 4 3 1 1 2 4 1 1 2 2 1 3 1
1 1 1 4 1 2 2 1 3
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 # Answer/Output
Can you help me write code for that problem?