This page is still under construction.

Parts of this page are still being built. What you see may change.

Random Generator

Time limit1sMemory limit1024 MB

Summary
Simulate repeatedly picking the p-th remaining copy from a multiset where value i appears w_i times, and output the order in which values are exhausted.
Level

Medium7 of 10

Topics
Segment tree, Binary search, Prefix sum, Simulation
Solved
No attempts yet

Problem

Gukryeol will randomly build a permutation of the positive integers from 1 to N using the given positive integers w1 ... , wN. The following is the method for randomly building the permutation.

  1. Place each positive integer i from 1 to N (1 ≤ i ≤ N) consecutively, wi copies at a time.
  2. Let W be the total number of positive integers currently placed. Choose one number pi uniformly at random from the positive integers 1 through W.
  3. Add the pi-th number to the permutation.
  4. Erase all the numbers added to the permutation, and repeat steps 2 through 4 until no numbers remain.

Given the numbers w1 through wN and p1 through pN, find the permutation that results.

Input

The first line gives N (1 ≤ N ≤ 200,000).

The second line gives the positive integers w1 through wN, each at most 1,000.

The third line gives the positive integers p1 through pN. Only cases in which a sequence can be built from p1 through pN are given.

Output

Find the sequence of positive integers from 1 to N that results at the end.

Examples2

  1. Example 1

    Input
    5
1 2 3 4 5
6 4 6 1 2
    Expected output
    3 4 5 1 2

  2. Example 2

    Input
    8
10 9 8 7 1 2 3 4
19 23 28 8 9 9 3 2
    Expected output
    2 4 8 1 5 6 3 7