<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

254. Strange Random
time limit per test: 0.25 sec.
memory limit per test: 9216 KB
input: standard
output: standard



Integer numbers from 1 to N are written in the increasing order, clockwise along the circle. You are moving from integer to integer sequentally. You start moving clockwise from 1.
Moving operation consists of the following steps:
1) You must count Q-th integer in your current moving direction and erase that integer.
2) Then you must move to the next integer clockwise.
3) If that integer is odd then your moving direction becomes clockwise (or nothing happens if you are already moving clockwise).
4) If that integer is even then your moving direction becomes counter-clockwise (or nothing happens if you are already moving counter-clockwise).

If there are no integers left you stop the moving process. Your goal is to find the last erased integer.
Let us consider the following example where N=5 and Q=3. The numbers will be deleted in the following order - 3, 1, 4, 5, 2. The last erased number is 2.

Input
The first line of input contains N and Q (1<=N<=2000000; 1<=Q<=10).

Output
Output the last erased integer.

Sample test(s)

Input
Test #1
5 2

Test #2
5 3

Output
Test #1
3

Test #2
2

Note
See picture:

Author:	Sergey Simonchik
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

<|response|>
1. Abridged problem statement
We have integers 1 through N arranged in a circle, labeled in increasing order clockwise. We start at label 1, moving clockwise. Repeatedly do the following until all numbers are removed:
  • From your current position, count Q labels in your current moving direction (the starting label counts as 1) and erase that Q-th label.
  • Move one step clockwise to the next remaining label.
  • If the label you land on is odd, set your moving direction to clockwise; if it is even, set your moving direction to counter-clockwise.
When the circle is empty, output the last erased label.

2. Key observations
- N can be as large as 2 000 000, Q≤10. A straightforward simulation in O(N·Q) is acceptable (≈2×10^7 steps).
- We need to support "step one forward/backward" and "remove a node" in O(1) time.
- A circular doubly linked list implemented with two arrays nxt[] and prv[] (size N+1) lets us do this in constant time per operation.

3. Full solution approach
- Build two arrays nxt[1..N] and prv[1..N], where nxt[i] is the label immediately clockwise from i, and prv[i] is the label immediately counter-clockwise from i.
- Initialize: for i=1..N, nxt[i]=i+1 (or 1 if i==N), prv[i]=i−1 (or N if i==1).
- Maintain:
    • current – the label you are "standing on" at the start of each erase step.
    • clockwise – a boolean for the current moving direction.
    • remaining – how many labels are left.
    • last_erased – the most recent erased label.
- While remaining>0:
    1. Let pos = current.
    2. Advance pos by Q−1 steps in the current direction:
         if clockwise: pos = nxt[pos]
         else:         pos = prv[pos]
    3. Erase pos:
         • last_erased = pos
         • link its neighbors: nxt[prv[pos]] = nxt[pos];  prv[nxt[pos]] = prv[pos]
         • remaining--
         • if remaining==0, break
    4. Move current = nxt[pos]  (always one step clockwise after erasure)
    5. Update direction: clockwise = (current is odd)
- At the end, last_erased is the answer.

Time complexity: O(N·Q). Memory: O(N).

4. C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, q;
vector<int> nxt, prv;

void read() { cin >> n >> q; }

void solve() {
    // Direct simulation on a doubly linked list over the circle 1..N, where
    // nxt[i] / prv[i] are the clockwise / counter-clockwise neighbours.
    // Starting at 1 moving clockwise, each step walks Q positions in the
    // current direction to the number to erase, unlinks it, then advances one
    // step clockwise. The parity of the number landed on after that step sets
    // the direction for the next step (odd -> clockwise, even ->
    // counter-clockwise). We keep going until the list is empty and report the
    // last erased number.

    nxt.resize(n + 1);
    prv.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        nxt[i] = (i == n) ? 1 : i + 1;
        prv[i] = (i == 1) ? n : i - 1;
    }

    int* nx = nxt.data();
    int* pv = prv.data();
    int current = 1;
    bool clockwise = true;
    int last_erased = -1;

    for(int remaining = n; remaining > 0; remaining--) {
        int pos = current;
        if(clockwise) {
            for(int i = 1; i < q; i++) {
                pos = nx[pos];
            }
        } else {
            for(int i = 1; i < q; i++) {
                pos = pv[pos];
            }
        }

        last_erased = pos;

        int next_pos = nx[pos];
        nx[pv[pos]] = next_pos;
        pv[next_pos] = pv[pos];

        current = next_pos;
        clockwise = (current & 1);
    }

    cout << last_erased << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys

def main():
    data = sys.stdin.read().split()
    N, Q = map(int, data)

    # nxt[i] is the next label clockwise; prv[i] is the next label counter-clockwise
    nxt = [i+1 for i in range(N+1)]
    prv = [i-1 for i in range(N+1)]
    nxt[N] = 1
    prv[1] = N

    current = 1          # start at label 1
    clockwise = True     # initial direction is clockwise
    remaining = N        # how many labels are left
    last_erased = -1     # to store the last erased label

    while remaining > 0:
        # 1) Find the Q-th label in the current direction
        pos = current
        for _ in range(Q-1):
            pos = nxt[pos] if clockwise else prv[pos]

        # 2) Erase pos
        last_erased = pos
        left, right = prv[pos], nxt[pos]
        nxt[left]  = right
        prv[right] = left
        remaining -= 1

        # If that was the last label, we're done
        if remaining == 0:
            break

        # 3) Move one step clockwise from the erased label
        current = right

        # 4) Update direction based on parity of current
        if current & 1:
            clockwise = True
        else:
            clockwise = False

    # Print the last erased label
    print(last_erased)

if __name__ == "__main__":
    main()
```
