We use the sieve of Eratosthenes to find the first ~K~ prime numbers.

Now we mark the square with ~0~ and circles with numbers ~1~ to ~N-1~. Since it would be impossible to simulate the entire game within the time limit, we first determine an algorithm that will help us find ~A~'s final position. Let's assume that currently ~A~ is on position ~x~ and the current prime is ~p~:

• If ~x = 0~, then ~A~ is in the square so ~x~ becomes ~N \bmod p~.
• Else, if ~x \ne 0~, then we can determine how many times the person in the square changes place with ~x~:
  • If ~x \le p \bmod (N-1)~ then ~x~ becomes ~(x-1) \bmod N~
  • Else ~x~ becomes ~(x - p \mathbin{\text{div}} (N-1)) \bmod N~

Where ~\bmod~ is the modulus operator and ~\text{div}~ is integer division. Now we need to solve the other way so that we may answer the question "If ~A~ is on ~X~ then who is on ~X-1~ (or ~X+1~)?"

Let's assume that we know position ~x~ after the prime ~p~ was played.

• If ~x = p \bmod N~, then ~x~ was at ~0~ before prime ~p~.
• Else, if ~x \ne p \bmod N~:
  • ~x~ becomes ~(x + p \mathbin{\text{div}} (N-1)) \bmod N~
  • If ~x \le p \bmod (N-1)~ then ~x~ becomes ~(x+1) \bmod N~

The time complexity is ~\mathcal O(K)~.