$3.$ In the card game War, a standard $52-$card deck is dealt to two players randomly so that each player ends up with a pile of $26$ cards. Let us call these players $1$ and $2.$ One wins the game by taking all of one's opponent's cards. Neither player looks at his or her cards. Instead, player $1$ removes the top card of his or her pile and places it face$-$up in the center of the table. Player $2$ does the same with the top card from his or her pile. Whoever flipped over the higher ranked card takes both cards in the center and adds them to the bottom of their packet in the reverse order they were revealed. For the purposes of deciding which card is the higher card, cards are ranked in the normal way $($with the Ace being the card of highest rank$)$ : $2,3,4,5,6,7,8,9,$ T$,$ J$,$ Q$,$ K$,$ A$.$ Suits are ignored. Both players then flip over the next card in their respective piles, again moving them to the center of the table and the process is repeated. This continues until one player wins by taking all of the cards.

When the face$-$up cards on any given turn are of the same rank, there is a war. When this happens, the initial cards played stay on the table to form a small pile to which the players alternatively add their next three cards face$-$down. Finally, they each add one more card, face$-$up$.$ These last two cards added face$-$up are again compared, and the player with the higher card takes all of the cards on the table $(10$ cards in total now$)$ and adds them to the bottom of their pile. Whenever cards are added to the bottom of a player's pile, they are always added in the reverse order as the cards were played $--$ specifically, player $1\text{'}$s first card, player $2\text{'}$s first card, player $1\text{'}$s second card, etc. Should this second pair compared result again in a tie, three more face$-$down cards are played, and then one more face$-$up$,$ with the player whose last card played is higher taking the entire stack of now $18$ cards. In the unlikely event that there should still be a tie, this process is repeated until there is no tie or until someone doesn't have enough cards to continue. Should a player not have enough cards to complete their turn, they lose.

You must simulate this game to predict on what turn the game ends and who wins given the initial states of the two players' piles.

Note:

Your program; for the cards that players hold should use queues, for the cards presented on the table should use a stack.

Your program should show the state of each player's pile on each turn, as shown in the sample run below. $($This will help debugging!$).$

Every time compared cards have the same rank, your program should print $"***$ WAR! $***",$ as shown in the sample run below. Note, this means that occasionally $($when multiple ties occur in the same turn$)$ that this message may be printed more than once on the same turn.

Some games might be infinite. As such, your program needs only to identify on which turn the game ends and who wins if the number of turns required to do so is less than $5000.$ Otherwise, declare the game a draw.

Sample run:

War

Enter Player $1\text{'}$s cards $($from top to bottom$)$:

$6$h $3$h Jc Ts $3$c $7$h $2$h $9$c $3$s $7$s $8$c $5$d Js Jh $6$d Ah Qh $9$d Ks $6$c Kc Td Jc Th $9$s Kd

Enter Player $2\text{'}$s cards $($from top to bottom$)$:

$3$d Qs Jd $8$d Ad Tc Qc $9$h $2$d $5$h $5$c $5$s $6$s $7$c $4$c $7$d Kh $8$s Ac $4$h $2$c Qd As $4$d $4$s $2$s

Turn: $1$

player$1$:

$6$h $3$h Jc Ts $3$c $7$h $2$h $9$c $3$s $7$s

$8$c $5$d Js Jh $6$d Ah Qh $9$d Ks $6$c

Kc Td Jc Th $9$s Kd

player$2$:

$3$d Qs Jd $8$d Ad Tc Qc $9$h $2$d $5$h

$5$c $5$s $6$s $7$c $4$c $7$d Kh $8$s Ac $4$h

$2$c Qd As $4$d $4$s $2$s

$--------------------------------------$

Turn: $2$

player$1$:

$3$h Jc Ts $3$c $7$h $2$h $9$c $3$s $7$s $8$c

$5$d Js Jh $6$d Ah Qh $9$d Ks $6$c Kc

Td Jc Th $9$s Kd $6$h $3$d

player$2$:

Qs Jd $8$d Ad Tc Qc $9$h $2$d $5$h $5$c

$5$s $6$s $7$c $4$c $7$d Kh $8$s Ac $4$h $2$c

Qd As $4$d $4$s $2$s

$--------------------------------------$

Turn: $3$

player$1$:

Jc Ts $3$c $7$h $2$h $9$c $3$s $7$s $8$c $5$d

Js Jh $6$d Ah Qh $9$d Ks $6$c Kc Td

Jc Th $9$s Kd $6$h $3$d

player$2$:

Jd $8$d Ad Tc Qc $9$h $2$d $5$h $5$c $5$s

$6$s $7$c $4$c $7$d Kh $8$s Ac $4$h $2$c Qd

As $4$d $4$s $2$s $3$h Qs

$--------------------------------------$

$***$ WAR! $***$

Turn: $4$

player$1$:

$9$c $3$s $7$s $8$c $5$d Js Jh $6$d Ah Qh

$9$d Ks $6$c Kc Td Jc Th $9$s Kd $6$h

$3$d

player$2$:

$9$h $2$d $5$h $5$c $5$s $6$s $7$c $4$c $7$d Kh

$8$s Ac $4$h $2$c Qd As $4$d $4$s $2$s $3$h

Qs Jc Jd Ts $8$d $3$c Ad $7$h Tc $2$h

Qc

$--------------------------------------$

$***$ WAR! $***$

$***$ WAR! $***$

Turn: $5$

player$1$:

Qh $9$d Ks $6$c Kc Td Jc Th $9$s Kd

$6$h $3$d $9$c $9$h $3$s $2$d $7$s $5$h $8$c $5$c

$5$d $5$s Js $6$s Jh $7$c $6$d $4$c Ah $7$d

player$2$:

Kh $8$s Ac $4$h $2$c Qd As $4$d $4$s $2$s

$3$h Qs Jc Jd Ts $8$d $3$c Ad $7$h Tc

$2$h Qc

$--------------------------------------$

Turn: $6$

player$1$:

$9$d Ks $6$c Kc Td Jc Th Th $9$s Kd $6$h

$3$d $9$c $9$h $3$s $2$d $7$s $5$h $8$c $5$c $5$d

$5$s Js $6$s Jh $7$c $6$d $4$c Ah