Snap

Snap is a two-player card game. The deck contains several copies of each type of card. At the start, each player holds one half of the deck as a face-down pile, in some fixed order, and plays the cards one at a time from the top, laying each one face up onto a second pile. When a player's face-down pile is exhausted, that player's face-up pile is turned over to become the new face-down pile, and play continues.

The two players play in lockstep: on every turn both players reveal the top card of their face-down pile at exactly the same instant. If the two revealed cards are of the same type, both players shout "Snap!", and whoever shouts first takes the other player's entire face-up pile and places it, keeping its order, on top of their own face-up pile.

Play continues until one player holds every card; that player wins.

Simulate a game of Snap to decide whether it finishes within 1000 turns and, if so, who wins.

The first line contains Jane's face-down pile, listed from top to bottom. The second line contains John's face-down pile, also from top to bottom. Each card type is a single letter or digit. Jane and John start with the same number of cards, at most 50 each.

Which player shouts "Snap!" first is decided by a fixed pseudo-random number generator. Let $x_0 = 11$ and

$$x_n = (1103515245 \cdot x_{n-1} + 12345) \bmod 2^{31}.$$

Each time a "Snap!" is called, advance the generator once; the $k$-th call uses the value $x_k$. If $\lfloor x_k / 141 \rfloor$ is even, Jane shouts first; otherwise John shouts first.

Every time Jane shouts first, print Snap! for Jane: followed by Jane's face-up pile from top to bottom (after she has taken John's pile). Every time John shouts first, print Snap! for John: followed by John's face-up pile from top to bottom (after he has taken Jane's pile). When the game ends, print Jane wins. or John wins., whichever applies. If the game has still not ended after each player has turned over 1000 cards, print Keeps going and going ....