OpenKattis
Kattis Set 12

#### Start

2020-04-06 05:15 AKDT

## Kattis Set 12

#### End

2020-04-13 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -569 days 5:13:53

164:15:00

0:00:00

# Problem LCrusaders of the Lost Mark

Apple Bloom, Sweetie Belle and Scootaloo are trying to discover their calling, and so they are trying various things to see what they are good at. Today, they decided to help ponies find suitable housing. They need to process the applications of ponies who want to settle down in the kingdom, and give suggestions based on their monthly income.

There are $A$ applications to process; the $i^\text {th}$ application contains $S_ i$, the monthly income of the $i^\text {th}$ applicant. For each application, they want to determine the best city to live that they can afford; that is, the city whose monthly cost of living is largest but still not exceeding their monthly income. It is guaranteed that each pony has at least one city they can afford to live in.

There are $C$ cities in Equestria, labelled $1, 2, \dots , C$, with costs of living $R_1, R_2, \dots , R_ C$, respectively. They don’t actually know the values of $R$; they only know that for all positive integers $i < C$, it holds $R_ i < R_{i+1}$.

They can call the national housing board to find out the cost of living in a particular city, but they have to pay an administrative fee of $\$ 1$each time. They only have$\$1\, 500$. Without exceeding their budget, help them determine where each pony should live!

## Interaction

First, your program should read two integers $C$ $(1 \leq C \leq 10^6)$ and $A$ $(1 \leq A \leq 106)$, the number of cities and the number of applications, respectively, on a single line from standard input.

Then, your program should read $A$ integers $S_1, S_2, \dots , S_ A$ $(R_1 \leq S_ i \leq 10^9)$, the monthly incomes of each pony, on a single line from standard input.

Then, we repeat the following process:

• Your program writes a single line to the standard output in either format: