Codeforces Round #481 (Div. 3)Petya's Exams CodeForces

Petya studies at university. The current academic year finishes with n.

There are three values about each exam:

i-th exam will be published,
si<di),
di−1, inclusive.

There are three types of activities for Petya in each day: to spend a day doing nothing (taking a rest), to spend a day passing exactly one exam or to spend a day preparing for exactly one exam. So he can't pass/prepare for multiple exams in a day. He can't mix his activities in a day. If he is preparing for the si≤j<di.

It is allowed to have breaks in a preparation to an exam and to alternate preparations for different exams in consecutive days. So preparation for an exam is not required to be done in consecutive days.

Find the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.

Input

The first line contains two integers (2≤n≤100,1≤m≤n) — the number of days and the number of exams.

Each of the following i-th exam.

Guaranteed, that all the exams will be in different days. Questions for different exams can be given in the same day. It is possible that, in the day of some exam, the questions for other exams are given.

Output

If Petya can not prepare and pass all the exams, print -1. In case of positive answer, print j-th number is:

j-th day is a day of some exam (recall that in each day no more than one exam is conducted),
zero, if in the j-th day Petya will have a rest,
$i$
Assume that the exams are numbered in order of appearing in the input, starting from 1.

If there are multiple schedules, print any of them.

Examples

Input

5 2
1 3 1
1 5 1

Output

1 2 3 0 3

Input

3 2
1 3 1
1 2 1

Output

-1

Input

Output

2 2 2 1 1 0 4 3 4 4

Note

In the first example Petya can, for example, prepare for exam 2 in the fifth day. So, he can prepare and pass all exams.

In the second example, there are three days and two exams. So, Petya can prepare in only one day (because in two other days he should pass exams). Then Petya can not prepare and pass all exams.

题意：

给你N天，和M个考试，

每一个考试有三个参数。

s是考试可以开始准备的日期。

e是考试日期（这一天必须考试，不能准备）

v，这个考试需要多少天。

每一天最多只能做一件事，要么这一天休息，要么准备考试，要么参加考试。

每一个考试必须在考试之前严格的准备了v天才能通过。

请你确定你是否能能过这M个考试，

如果不可以，只需要输出-1

否则输出每一天i是做什么事情，休息是0，考试是m+1，准备是准备的那个考试编号。

思路：

贪心题，

按照每一个考试的考试日期由近到远排序。

然后枚举每一个天,1~n

如果这一天没有被使用，去检查最近1~m哪一个考试在第 i 天准备。

如果可以填就填，这样贪心搞。

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d
",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ' ', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
struct node
{
    int s;
    int e;
    int v;
    int id;
}a[200];
int n,m;
int vis[2222];
bool cmp(node aa,node bb)
{
    return aa.e<bb.e;
}
int main()
{
    //freopen("D:common_textcode_streamin.txt","r",stdin);
    //freopen("D:common_textcode_streamout.txt","w",stdout);
    gbtb;
    cin>>n>>m;
    repd(i,1,m)
    {
        cin>>a[i].s>>a[i].e>>a[i].v;
        a[i].id=i;
        vis[a[i].e]=m+1;
    }
    sort(a+1,a+1+m,cmp);
    repd(i,1,n)
    {
        if(vis[i])
        {
            continue;
        }
        repd(j,1,m)
        {
            if(!a[j].v)
            {
                continue;
            }
            if(a[j].e>i&&a[j].s<=i)
            {
                vis[i]=a[j].id;
                a[j].v--;
                break;
            }
        }
    }
    repd(i,1,m)
    {
        if(a[i].v)
        {
            cout<<-1<<endl;
            return 0;
        }
    }
    repd(i,1,n)
    {
        cout<<vis[i]<<" ";
    }
    cout<<endl;



    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

Codeforces Round #481 (Div. 3)Petya's Exams CodeForces

相关推荐