Card Shuffle

Problem code: CARDSHUF

All submissions for this problem are available.

Chef is organizing an online card game tournament and for this purpose he has to provide a card shuffling software. This software has to simulate the following shuffling process. A stack of N cards is placed face down on the table. Cards in the stack are ordered by value. Topmost card has value 1 and the one on the bottom has value N. To shuffle the cards we repeat the following steps M times:

  1. take A cards from the top of the deck.
  2. take another B cards from the top of the deck.
  3. put the A cards, which you removed in the first step, back on top of the remaining deck.
  4. take C cards from the deck
  5. put the B cards, which you're still holding from the second move, card by card on top of the deck.
  6. finally, return the block of C cards on top
Note: taking a block of cards from the top of the deck does not change their order. The entire block is removed in a single move and not card by card. The only exception is the fifth move, where you return cards one by one from the top.

Input

The first line contains integers N and M. The following M lines describe the moves by integers Ai, Bi, Ci as described in the previous section.

In the spirit of random card shuffling, all test cases were generated with uniform random distributions to select where to cut the deck of cards.

Output

In a single line output the cards in the deck after performing all the moves. Cards should be listed from top of the deck to bottom and separated by spaces.

Constraints

  • 1 <= N, M <= 100 000

Example

Input:
10 2
6 2 2
5 3 6

Output:
1 2 8 7 3 9 6 5 4 10

Author: thocevar
Tester: laycurse
Editorial http://discuss.codechef.com/problems/CARDSHUF
Date Added: 7-12-2011
Time Limit: 6 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

i think the in the output we

ron2794 @ 1 Jan 2012 03:20 PM
i think the in the output we will get two lines is it ?

@ron2794 Why? Output should

hiroto_adm @ 1 Jan 2012 03:48 PM
@ron2794 Why? Output should be the cards in the deck after performing *all* the moves

oh ok..i counted those lines

ron2794 @ 1 Jan 2012 04:29 PM
oh ok..i counted those lines as test cases.........allowing only one move described above at a time.

can a,b,c equal to 0 ?

imchaitanya @ 1 Jan 2012 06:47 PM
can a,b,c equal to 0 ?

B is at least 1 in the test

tomaz_adm @ 1 Jan 2012 07:02 PM
B is at least 1 in the test cases. A and C can be 0.

Dear admin, I keep getting

acpaluri @ 1 Jan 2012 08:28 PM
Dear admin, I keep getting the TLE error. The program (submission no. 774508) is working for the given test cases. Can you please check why it is giving TLE. Thanks.

my code is working fine..on

sumit4iit @ 2 Jan 2012 10:55 AM
my code is working fine..on my pc..bt codechef is giving is giving runtime error.. will u please tell me where is the error??

can the number of cards in

sumit4iit @ 2 Jan 2012 10:57 AM
can the number of cards in the deck (on table ) be zero?

how can onlyn_judge accept

sumit4iit @ 2 Jan 2012 11:03 AM
how can onlyn_judge accept solutions taking time more than 6s ...??

what is the higher limit of n

vamsi_algo @ 2 Jan 2012 12:45 PM
what is the higher limit of n

can you provide more test

imscorpion @ 2 Jan 2012 02:09 PM
can you provide more test cases .. Its hard to test ur logic and code just on the basis of one ...

@sumit4iit: I checked your

tomaz_adm @ 2 Jan 2012 03:30 PM
@sumit4iit: I checked your solution and found the problem but it's up to you to debug it. Yes, there might be 0 cards on the table at some point. http://www.codechef.com/wiki/faq#How_does_the_time_limit_work

@vamsi_algo: I think it's

tomaz_adm @ 2 Jan 2012 03:30 PM
@vamsi_algo: I think it's clear that the upper bound for N and M is 100 000.

@imscorpion: Further cases

tomaz_adm @ 2 Jan 2012 03:31 PM
@imscorpion: Further cases will not be provided but you can always make some yourself. It's not forbidden, actually it's very encouraged. :) The point of provided test cases is to clear up any ambiguities in the problem statement, not to test your solutions.

@admin: what should happen

acpaluri @ 2 Jan 2012 03:49 PM
@admin: what should happen when you try to pick more cards than available ?

@acpaluri: Test cases contain

tomaz_adm @ 2 Jan 2012 05:04 PM
@acpaluri: Test cases contain valid inputs, this will not happen.

I tried may times... It's

jainharshit @ 2 Jan 2012 07:02 PM
I tried may times... It's still giving TLE.... m confused what to do now ..!!!

Will brute force algorithm

jainharshit @ 3 Jan 2012 01:17 AM
Will brute force algorithm work here or not?

@jainharshit: You have to

tomaz_adm @ 3 Jan 2012 02:00 AM
@jainharshit: You have to figure that out on your own. Do not ask for hints. Answering that kind of question is grounds for disqualification.

@admin: I'm getting TLE using

samridh90 @ 4 Jan 2012 09:00 AM
@admin: I'm getting TLE using Python-2.5.. Submission 778599.. Could you please let me know what the issue is?

What can be the maximum

nikhil_kataria @ 4 Jan 2012 11:14 PM
What can be the maximum values for A,B,C?

@nikhil_kataria: As

tomaz_adm @ 5 Jan 2012 01:20 AM
@nikhil_kataria: As previously mentioned, the values are such that it is possible to pick up the given amount of cards from the deck.

i keep getting a compile

saikat_roy @ 6 Jan 2012 11:41 PM
i keep getting a compile error while my code seemingly works fine on my IDE....will u plz tel me where is the error...

got rid of that error and got

saikat_roy @ 7 Jan 2012 12:14 AM
got rid of that error and got another one.. -_-

where l be runtime error

codingguru @ 7 Jan 2012 01:05 PM
where l be runtime error

@admin my submission id is

sehrawat.parshant @ 7 Jan 2012 05:39 PM
@admin my submission id is 781297 got runtime error could u please tell me exactly what type of error is this

@sehrawat.parshant: I can't

tomaz_adm @ 7 Jan 2012 06:06 PM
@sehrawat.parshant: I can't give you more information than what is described in http://www.codechef.com/wiki/faq#Why_do_I_get_a_Runtime_exception

@admin: My submission has an

rahulsuresh @ 7 Jan 2012 06:31 PM
@admin: My submission has an extra space and newline at the end of the answer. Will that be considered as a wrong answer?

@rahulsuresh: Extra

tomaz_adm @ 7 Jan 2012 08:59 PM
@rahulsuresh: Extra whitespaces are ignored by the judge for this problem. Your answer would be correct if the numbers matched.

i am getting run time error

manovagyanik @ 8 Jan 2012 12:19 PM
i am getting run time error on submission but it is working on my pc. can you please help.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions