Given a deck of cards of size n where the cards are labelled from 1 to n and a number k where k is the number of cards shuffled at each step.

Step 1; Shuffle - Bring the top k cards to the bottom of the deck.
Step 2: Remove the card at the top.
Step 3: Repeat steps 1 and 2 until you are left with 1 card in the deck.

Return the card.

1 <= k <= n <= 1000000

Example:
Input: n = 6, k = 4
Output: 1
Explanation:
Start off with cards 123456.
After shuffling, the deck becomes 561234. Remove the top card and the deck becomes 61234.
Repeat.
123456 -> 561234 -> 61234 -> 46123 -> 6123 -> 6123 -> 123 -> 231 -> 31 -> 31 -> 1.

My solution was to use a queue. To shuffle the cards, just remove the card at the front of the queue and insert it back in, for a total of k times. To remove the top card, poll from the queue. Repeat until my queue is of size 1.

Time complexity is O(nk) and I got a TLE for one of the test cases, when n = 1000000 and k = 50000. How should I solve this?

Clarification: When the number of cards remaining is less than k, the cards are still being shuffled. e.g. when the deck is 123, and we shuffle four times, the deck becomes 231 -> 312 -> 123 -> 231.