题目描述

有一位美食博主来探店一家新开的自助餐厅。刚一进店，就被各种琳琅满目的菜品惊艳到了。这时，他想起来了粉丝们的嘱托：“一定要尽可能吃回本！”。已知博主的最大饭量为$m$。餐厅今日一共提供$n$种菜品，每种菜品有它自己的菜品名字$s$（$s$为一个长度不超过50的字符串），总量$p$和市场总价$q$，以及菜品的荤素情况$0/1$（0代表荤菜，1代表素菜），请问如果想尽可能回本，且在尽可能优先吃荤菜的情况下。输出吃菜的顺序。

注：吃到但未吃完的菜算吃过！

输入格式

第一行输入博主的最大饭量$m$以及菜品的总数$n$。

第2~第n+1行输入每道菜品的名字$s$，总量$p$，市场总价$q$，菜品的荤素情况$0/1$。

输出格式

输出占一行，为吃菜的顺序（按输入时的顺序输出）。

60 5
boiled-vegetable 20 120 1
coke 30 90 1
Boston-lobster 10 1000 0
ham 20 120 0
noodles 20 40 1

3 4 1 2

样例解释

3，4，1，2分别代表输入的第三个菜品Boston-lobster，第四菜品ham，第一菜品boiled-vegetable，第二菜品coke。

也就代表着吃菜顺序为Boston-lobster -> ham -> boiled-vegetable -> coke。

数据规模与约定

对于100%的数据，1<=m<=100000，1<=n<=100，1<=p，q<=1000，数据保证q是p的整数倍。