Rouba-Monte

Simulate a card game where players draw, steal montes, and discard mismatches; report the winners by monte size.

Medium5SimulationImplementationArrayHash mapInterviewNo attempts yetTime limit1sMemory limit512 MB

Problem

Rouba-Monte is a card game simple enough for small children. It uses one or more ordinary decks, and cards are told apart only by their value (ace, two, three, ...). Suits do not count, so the ace of clubs and the ace of diamonds are the same card.

At the start the cards are shuffled and placed face down in one stack on the table. That stack is the draw pile. During the game every player keeps a face up pile of cards called a monte. A monte holds zero or more cards, and every monte is empty when the game begins. Next to the draw pile is the discard area, empty at the start. Cards put in the discard area are laid side by side face up, never stacked.

The players sit in a circle around the table and take turns clockwise. A turn goes like this.

  • The player whose turn it is takes the top card of the draw pile and shows it to the others. Call it the current card.
  • If the current card has the same value as some card in the discard area, the player takes that card out of the discard area and puts it, together with the current card, face up on top of his own monte, then continues the turn. That is, he takes another card from the draw pile and repeats the process.
  • If the current card has the same value as the top card of another player's monte, the player steals that monte, stacks it on his own, puts the current card face up on top, then continues the turn.
  • If the current card has the same value as the top card of his own monte, the player puts the current card face up on top of his own monte, then continues the turn.
  • If the current card differs in value from every card in the discard area and from the top card of every monte, the player puts it face up in the discard area and the turn ends. This is the only case in which the turn ends.

The game ends when the draw pile has no cards left. The player whose monte holds the most cards wins. If several players tie for the most cards, all of them win.

Given the order of the cards in the draw pile, find the players who win.

Input

The input holds several test cases. The first line of a test case has two integers N and J, the number of cards in the draw pile (2N100002 \le N \le 10000) and the number of players (2J202 \le J \le 20, JNJ \le N). Cards are written as integers from 1 to 13, and players are identified by integers from 1 to J. Player 1 plays first, then player 2, ..., then player J, then player 1 again, and so on for as long as the draw pile has cards. The second line has N integers between 1 and 13 separated by single spaces, the cards of the draw pile. Cards leave the draw pile in the order they appear in the input. The end of the input is a line with N and J both equal to 0.

Output

For each test case print one line with the number of cards in the monte of the winning player or players, then a single space, then the identifiers of the winning players. If more than one player wins, print the identifiers in increasing order, separated by single spaces.