Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Quarantiko

By Riaz_BSMRSTU · 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 

Discussion

Statistics


66% Solution Ratio

iammarajulEarliest, 1M ago

emrul_muFastest, 0.0s

fuadulhasanLightest, 786 kB

Abdullah_SheehanShortest, 396B

Submit

Login to submit