A royal mint runs several production batches side by side, one furnace per batch, and every batch keeps its own separate ledger — nothing raised or spent in one batch ever touches another. Batch i begins with count[i] unstruck coin blanks sitting in its furnace and money[i] gold pieces already in its treasury. Reminting one blank into a finished coin costs upgrade[i] gold. Any blank that is not going to be reminted may instead be melted down and sold as scrap silver for sell[i] gold apiece — the mint master may melt down anywhere from zero up to all of the blanks that are being left unreminted.

For each batch, using only that batch's own treasury plus the scrap gold raised from melting the blanks that are not reminted, determine the maximum number of blanks that can be reminted.

Input format

• Line 1: a single integer n, the number of mint batches.
• Line 2: n integers count[1..n].
• Line 3: n integers upgrade[1..n].
• Line 4: n integers sell[1..n].
• Line 5: n integers money[1..n].

Output format

Print n integers separated by single spaces on one line: for each batch i, the maximum number of blanks that can be reminted.

Constraints

• 1 <= n <= 10^5
• 1 <= count[i] <= 10^9
• 1 <= upgrade[i] <= 10^9
• 0 <= sell[i] <= 10^9
• 0 <= money[i] <= 10^9

1
4
3
1
2

1

2
5 3
2 10
3 1
0 50

3 3