RoAlgo PreOJI 2024 X | pofta

Task

$N$ people are standing on the $Ox$ axis. For each person, you have two arrays of $N$ elements $d$ and $f$, where

$d_i = \text{the distance of person } i \text{ from the origin} \newline f_i = \text{the "beauty" of person } i$
The people are labeled such that the array $d$ is in ascending order.

Each person wants to find their soulmate, so a compatibility index has been created. Person $i$ is willing to travel at most $depmax_i$ meters to another person (including themselves), but for each meter traveled, the compatibility decreases by a global coefficient. Formally, the compatibility between two people is defined as:

Display for each person who is the suitable person (the index of the person where the compatibility is maximum).

Attention: It is ensured that the positions where they will travel the most $^1$ (see constraints) are in ascending order. We can think that, the further people are from the origin, the less motivated they are to travel so much.

Input data

The first line of the input file pofta.in contains two natural numbers $N$ and $coef$. The next $3$ lines contain the arrays $d$, $f$, and $depmax$, all with the significance given in the task.

Output data

The first line of the output file pofta.out will contain an array of $N$ natural numbers $c$ with the property that $comp(i, c_i)$ is maximum for each $i$ (of course $1 \leq i \leq N$)

Constraints and clarifications

• $1 \leq N \leq 1 \ 000 \ 000$;
• $0 \leq d_i, depmax_i, f_i \leq 10^{10}$
• $1 \leq coef \leq 1 \ 000$
• $^1$ Let $l_i$ and $r_i$ be the leftmost and rightmost positions person $i$ can reach, respectively: $l_i \leq l_{i+1}$ and $r_i \leq r_{i+1}$ for each $1 \leq i < N$
• For each $i$, $c_i$ is unique

Example 1

pofta.in

5 1
2 6 9 13 14
9 14 10 7 14
5 3 1 2 3

pofta.out

2 2 3 5 5

Explanation

The 5 people on the $Ox$ axis and their accessibility:

The values $comp(i, j)$ are written in the table below. We leave the cells empty where $dist(i, j) > depmax_i$.