#R2024A0004. Music Game

Music Game

Problem: Music Game

时间限制:1s

空间限制:256MB

Description

​ 原力清理大师最近迷上音游了!但是随着谱子难度的增加,要打的按键越来越多,由于原力清理大师反应迟钝,不仅手速跟不上,连读谱(即判断在某一时刻应该处理哪些按键)都来不及,故而前来寻求你的帮助。

​ 特别的,由于原力清理大师实在是太菜了,所以只存在需要单点的按键需要处理(即不存在需要长按的按键或者其他特殊形式的按键)。现在,有四条并排的路,每条路上会有若干音符按键接近判定线。现在,原力清理大师仔细研究了这些音符按键,并且告诉你每个按键初始时到达判定线所需的时间以及它具体在哪一条路(依次标记为 11223344),你需要输出原力清理大师要拿满分需要击打哪一条路的音符(无需输出击打时对应的时间,如果还是不能理解请看样例)。

Input Format

第一行一个数字 nn ,代表音符数量。

第二行到第 n+1n+1 行,每行两个数字,第一个数字代表该音符到达判定线所需的时间,第二个数字代表次音符在哪一条路。

Output Format

输出一行 nn 个数字,每个数字代表原力清理大师此时需要击打哪一条路的音符。若两赛道的音符同时到达,则按照编号顺序从小到大输出。

Data Range

  • 1n1e51 \leq n \leq 1e5 (即 101055 次方);
  • 对于第 ii 个音符到达所需时间 tit_i1in1 \leq i \leq n ),有 1ti1e181 \leq t_i \leq 1e18
  • 对于第 ii 个音符所在赛道编号 sis_i ,有 1si41 \leq s_i \leq 4

Input Example #1:

4
5 1
2 4
3 3
6 2

Output Example #1:

4 3 1 2

Explanation

最近的音符为第四赛道的音符,所需时间为 22 ;其次为第三赛道的音符,所需时间为 33 ;第三个为第一赛道的音符,所需时间为 55 ;最后一个为第二赛道的音符,所需时间为 66

所以依次输出 43124 3 1 2