Limits 2s, 512 MB

"If you feel unwell, stay home."

Riaz has created a special encryption algorithm named Quarantiko to encrypt any array of consisting 0 and 1. He encrypted an array and gave you the encrypted array and the encrypted keys. He gave you a challenge to decrypt it.

You will be given the encrypted array and encrypted keys for every index. You have to find the real array.
(Here encrypted key of any index is the Quaran cost between the prefix of encrypted array till this index and the real array).

Suppose, given encrypted array {1, 1, 1, 1, 1} and encrypted keys {4, 3, 3, 3, 2}. Here, 1st key 4 is the Quaran cost between prefix {1} and the real array, 2nd key 3 is the Quaran cost between prefix {1, 1} and the real array and so on.

Note: Quaran cost of two arrays A and B is a value equal to the minimum number of one-element operations of replacing any element in A or inserting element at right side in A to get B. For example, the cost between A{1, 0, 1} and B{1, 1, 1} is 1, the cost between A{1, 1} and B{1, 0, 1} is 2, the cost between A{1, 0, 1} and B{0, 1, 0} is 3. The Quaran cost is 0 if and only if the arrays are equal.

Input

The first line will contain a number N (1 ≤ N ≤ 1e5), the length of arrays.
Next line contains N numbers (0 ≤ a1, a2…an ≤ 1), where ai represent the ith element of encrypted array.
Next line contains N numbers (0 ≤ c1, c2…cn ≤ 1e5), where ci represent the encrypted key of ith index.

Output

N space separated numbers which denotes your real array.

Sample

InputOutput
5
1 1 1 1 1
4 3 3 3 2

1 1 0 0 1 

Submit

Login to submit.

Statistics

71% Solution Ratio
iammarajulEarliest, Apr '20
user.123Fastest, 0.0s
md_jakariyaLightest, 524 kB
mumith_fahim99Shortest, 323B
Toph uses cookies. By continuing you agree to our Cookie Policy.