#P1571F. Kotlinforces
-
ID: 1848
Type: RemoteJudge
2000ms
512MiB
Tried: 0
Accepted: 0
Difficulty: 7
Uploaded By:
Hydro
Tags> Kotlinforces
Description
Kotlinforces is a web platfrom that hosts programming competitions.
The staff of Kotlinforces is asked to schedule programming competitions on the next days. Each competition is held in multiple stages; the regulations of the -th competition state that this competition should consist of exactly stages, and each stage, starting from the second one, should be scheduled exactly days after the previous stage. In other words, if the first stage of the -th competition is scheduled on day , the second stage should be scheduled on day , the third stage — on day , ..., the -th stage (which is the last one) — on day .
All competitions should be scheduled in such a way that they start and finish during the next days, and on any of these days, at most one stage of one competition is held (two stages of different competitions should not be scheduled on the same day).
Is it possible to schedule all competitions to meet these constraints?
The first line contains two integers and () — the number of competitions and the number of days, respectively.
Then lines follow, each describing a competition which should be scheduled. The -th line contains two integers and (; ) — the parameters of the -th competition.
If it is impossible to schedule all competitions on the next days so that there is at most one stage during each day, print -1.
Otherwise, print integers. The -th integer should represent the day when the first stage of the -th competition is scheduled; days are numbered from to . If there are multiple answers, print any of them.
Input
The first line contains two integers and () — the number of competitions and the number of days, respectively.
Then lines follow, each describing a competition which should be scheduled. The -th line contains two integers and (; ) — the parameters of the -th competition.
Output
If it is impossible to schedule all competitions on the next days so that there is at most one stage during each day, print -1.
Otherwise, print integers. The -th integer should represent the day when the first stage of the -th competition is scheduled; days are numbered from to . If there are multiple answers, print any of them.