cf----2019-10-12（Bus Video System，Bus Video System，Petya's Exams）_bussex

一场游戏一场空，最终 最初都由我掌控，好像一身从容，不曾有狼狈伤痛，可深夜一个人该如何相拥？

 

The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.

If xx is the number of passengers in a bus just before the current bus stop and yy is the number of passengers in the bus just after current bus stop, the system records the number y−xy−x. So the system records show how number of passengers changed.

The test run was made for single bus and nn bus stops. Thus, the system recorded the sequence of integers a1,a2,…,ana1,a2,…,an (exactly one number for each bus stop), where aiai is the record for the bus stop ii. The bus stops are numbered from 11 to nn in chronological order.

Determine the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to ww (that is, at any time in the bus there should be from 00 to ww passengers inclusive).

Input

The first line contains two integers nn and ww (1≤n≤1000,1≤w≤109)(1≤n≤1000,1≤w≤109) — the number of bus stops and the capacity of the bus.

The second line contains a sequence a1,a2,…,ana1,a2,…,an (−106≤ai≤106)(−106≤ai≤106), where aiai equals to the number, which has been recorded by the video system after the ii-th bus stop.

Output

Print the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to ww. If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print 0.

Examples

input

Copy

3 5
2 1 -3

output

Copy

3

input

Copy

2 4
-1 1

output

Copy

4

input

Copy

4 10
2 4 1 2

output

Copy

2

Note

In the first example initially in the bus could be 00, 11 or 22 passengers.

In the second example initially in the bus could be 11, 22, 33 or 44 passengers.

In the third example initially in the bus could be 00 or 11 passenger.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll n,w,a;
int main()
{
    cin>>n>>w;
    ll sum=0;
    ll mx=0,mi=w;
    while(n--)
    {
        cin>>a;
        sum+=a;
        mx=max(mx,-sum);
        mi=min(mi,w-sum);
    }
    if(mx<=mi)
        printf("%d\n",mi-mx+1);
    else
        printf("0\n");
    return 0;
}

After the big birthday party, Katie still wanted Shiro to have some more fun. Later, she came up with a game called treasure hunt. Of course, she invited her best friends Kuro and Shiro to play with her.

The three friends are very smart so they passed all the challenges very quickly and finally reached the destination. But the treasure can only belong to one cat so they started to think of something which can determine who is worthy of the treasure. Instantly, Kuro came up with some ribbons.

A random colorful ribbon is given to each of the cats. Each color of the ribbon can be represented as an uppercase or lowercase Latin letter. Let's call a consecutive subsequence of colors that appears in the ribbon a subribbon. The beauty of a ribbon is defined as the maximum number of times one of its subribbon appears in the ribbon. The more the subribbon appears, the more beautiful is the ribbon. For example, the ribbon aaaaaaa has the beauty of 77 because its subribbon a appears 77 times, and the ribbon abcdabc has the beauty of 22because its subribbon abc appears twice.

The rules are simple. The game will have nn turns. Every turn, each of the cats must change strictly one color (at one position) in his/her ribbon to an arbitrary color which is different from the unchanged one. For example, a ribbon aaab can be changed into acab in one turn. The one having the most beautiful ribbon after nn turns wins the treasure.

Could you find out who is going to be the winner if they all play optimally?

Input

The first line contains an integer nn (0≤n≤1090≤n≤109) — the number of turns.

Next 3 lines contain 3 ribbons of Kuro, Shiro and Katie one per line, respectively. Each ribbon is a string which contains no more than 105105 uppercase and lowercase Latin letters and is not empty. It is guaranteed that the length of all ribbons are equal for the purpose of fairness. Note that uppercase and lowercase letters are considered different colors.

Output

Print the name of the winner ("Kuro", "Shiro" or "Katie"). If there are at least two cats that share the maximum beauty, print "Draw".

Examples

input

Copy

3
Kuroo
Shiro
Katie

output

Copy

Kuro

input

Copy

7
treasurehunt
threefriends
hiCodeforces

output

Copy

Shiro

input

Copy

1
abcabc
cbabac
ababca

output

Copy

Katie

input

Copy

15
foPaErcvJ
mZaxowpbt
mkuOlaHRE

output

Copy

Draw

Note

In the first example, after 33 turns, Kuro can change his ribbon into ooooo, which has the beauty of 55, while reaching such beauty for Shiro and Katie is impossible (both Shiro and Katie can reach the beauty of at most 44, for example by changing Shiro's ribbon into SSiSSand changing Katie's ribbon into Kaaaa). Therefore, the winner is Kuro.

In the fourth example, since the length of each of the string is 99 and the number of turn is 1515, everyone can change their ribbons in some way to reach the maximal beauty of 99 by changing their strings into zzzzzzzzz after 9 turns, and repeatedly change their strings into azzzzzzzz and then into zzzzzzzzz thrice. Therefore, the game ends in a draw.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n, p[5];
char a[100010];
map<char, int> mp;
map<char, int> :: iterator it;
int fd(char *s)
{
    mp.clear();
    int cd = strlen(s), mx = 0;
    for(int i = 0; i < cd; i++)
        mp[s[i]]++;
    for(it = mp.begin(); it != mp.end(); it++)
        mx = max(mx, (it->second));
    if(n == 1&&mx == cd)
        mx = cd - 1;
    else if(cd - mx >= n)
        mx += n;
    else
        mx = cd;
    return mx;
}
bool cmp(int mx)
{
    if((p[0] == mx&&p[1] == mx)||(p[0] == mx&&p[2] == mx)||(p[1] == mx&&p[2] == mx))
        return true;
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < 3; i++)
    {
        scanf("%s", a);
        p[i] = fd(a);
    }
    int mx = max(p[0], max(p[1], p[2]));
    if(cmp(mx))
        printf("Draw\n");
    else if(p[0] == mx)
        printf("Kuro\n");
    else if(p[1] == mx)
        printf("Shiro\n");
    else if(p[2] == mx)
        printf("Katie\n");
    else
        printf("Draw\n");
    return 0;
}

Petya studies at university. The current academic year finishes with nn special days. Petya needs to pass mm exams in those special days. The special days in this problem are numbered from 11 to nn.

There are three values about each exam:

• sisi — the day, when questions for the ii-th exam will be published,
• didi — the day of the ii-th exam (si<disi<di),
• cici — number of days Petya needs to prepare for the ii-th exam. For the ii-th exam Petya should prepare in days between sisi and di−1di−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 ii-th exam in day jj, then si≤j<disi≤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 nn and mm (2≤n≤100,1≤m≤n)(2≤n≤100,1≤m≤n) — the number of days and the number of exams.

Each of the following mm lines contains three integers sisi, didi, cici (1≤si<di≤n,1≤ci≤n)(1≤si<di≤n,1≤ci≤n) — the day, when questions for the ii-th exam will be given, the day of the ii-th exam, number of days Petya needs to prepare for the ii-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 nnintegers, where the jj-th number is:

• (m+1)(m+1), if the jj-th day is a day of some exam (recall that in each day no more than one exam is conducted),
• zero, if in the jj-th day Petya will have a rest,
• ii (1≤i≤m1≤i≤m), if Petya will prepare for the ii-th exam in the day jj (the total number of days Petya prepares for each exam should be strictly equal to the number of days needed to prepare for it).

  Assume that the exams are numbered in order of appearing in the input, starting from 11.

  If there are multiple schedules, print any of them.

Examples

input

Copy

5 2
1 3 1
1 5 1

output

Copy

1 2 3 0 3 

input

Copy

3 2
1 3 1
1 2 1

output

Copy

-1

input

Copy

10 3
4 7 2
1 10 3
8 9 1

output

Copy

2 2 2 1 1 0 4 3 4 4 

Note

In the first example Petya can, for example, prepare for exam 11 in the first day, prepare for exam 22 in the second day, pass exam 11 in the third day, relax in the fourth day, and pass exam 22 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.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct node
{
    int ks;
    int js;
    int xz;
    int xh;
} p[110];
int n,m;
int s[110];
bool flag = true;
int cmp(node a,node b)
{
    return a.js<b.js;
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&p[i].ks,&p[i].js,&p[i].xz);
        p[i].xh = i;
    }
    sort(p+1,p+m+1,cmp);
    for(i=1; i<=m; i++)
    {
        if(s[p[i].js]==0)
            s[p[i].js] = m+1;
        else
            flag = false;
    }
    for(i =  1; i<=m; i++)
    {
        for(j = p[i].ks; j<=p[i].js; j++)
        {
            if(s[j]==0)
            {
                s[j] = p[i].xh;
                p[i].xz--;
            }
            if(p[i].xz==0)
                break;
        }
        if(j>p[i].js)
            flag = false;
    }
    if(!flag)
        printf("-1\n");
    else
    {
        for(int i = 1; i<=n; i++)
            printf("%d ",s[i]);
        printf("\n");
    }
    return 0;
}