<|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.

363. Baggage Room
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Schoolboys Vasya and Pete travel a lot. They use baggage rooms really often. Baggage room has M windows, numbered 1 through M. When a lot of people come, there are big queues in front of windows. Newly come person stands in the queue with the least number of people. If there are several such queues than he or she chooses queue to the window with lowest number. When the queue is chosen, the decision will not further change. When next person comes to the window, he or she spends some time near the window to take or get his stuff, pay money, etc. (let's call it servicing time). This time is specific to each person and doesn't depend on the window. During this time the person is counted as standing in the queue. If new person come in the moment when one or several peoplehave just proceeded to their windows, he or she waits first until these people will leave their queues and then he or she chooses the queue to stand in. Vasya and Pet e wonder when each particular person will leave the queue. Please help them.

Input
The first line of the input file contains two integer numbers N, M (1 ≤ N ≤ 100; 1 ≤ M ≤ 100), where N - number of people, M - number of windows in the baggage room. Next N lines contain pairs of integer numbers ki, ti (1 ≤ ki ≤ 1000; 1 ≤ ti ≤ 100), where ki - time moment, when ith person came, ti - servicing time of ith person. Persons are listed in order of increase of ki.

Output
Print N lines. Print in the ith line two numbers - number of the queue, that would be chosen by ith person and moment of the time, when he or she will leave the queue.

Example(s)
sample input
sample output
5 2
1 2
3 4
4 1
5 2
6 1
1 3
1 7
2 5
2 7
1 8

<|response|>
1. Abridged problem statement
-----------------------------

There are `M` service windows (1..M) and `N` people.

- Person `i` arrives at time `k_i` and needs `t_i` units of service time.
- Arrivals are given in non-decreasing order of `k_i`.

When a person arrives at time `k`:

1. First, everyone whose service has already finished at or before time `k` is removed from their queues.
2. Then the person chooses a window:
   - Count how many people are currently in each window’s queue (including the one being served).
   - Choose the window with the *smallest* number of people; if several, choose the smallest window index.
3. Once a window is chosen, it never changes.
4. At each window, people are served one by one in the order they joined that window; service for a person starts at:
   - `max(their arrival time, previous person’s finish time at that window)`.
   Their finish time is that start time plus their service time.

For every person, output:

- The window number they chose.
- The time when they finish service (leave the queue).

Constraints: `1 ≤ N, M ≤ 100`, `1 ≤ k_i ≤ 1000`, `1 ≤ t_i ≤ 100`.


2. Key observations
-------------------

1. **“In queue” definition.**
   A person is considered to be in a window’s queue from the moment they join it until their service finishes.
   Formally, if a person finishes at time `f`, they are in queue during times `(join_time, f]`.

2. **Event order at equal times.**
   If a person arrives at time `k`, and some people finish exactly at `k`, those finishers must be removed before deciding the newcomer’s queue.
   That means: at time `k`, a person is in queue **only if** `finish_time > k`.

3. **Sequential service per window.**
   Each window serves people one at a time:
   - First person in that window:
     `start = arrival`, `finish = start + service_time`.
   - Later persons in that window:
     `start = max(arrival, last_finish_at_window)`,
     `finish = start + service_time`.

4. **Small constraints allow simple simulation.**
   With `N ≤ 100` and `M ≤ 100`, we can afford an `O(N^2)` or even `O(N^3)`-ish solution. No need for complicated data structures.

5. **State needed per window.**
   To know when a window is free and how many people it currently has:
   - Store the list of finish times of all people that chose this window, in the order they joined.
   - At an arrival time `k`, the queue length for window `w` is:
     `count of finish_times[w] that are > k`.

   Also, the **last** finish time in `finish_times[w]` is enough to compute the next start time at that window.


3. Full solution approach
-------------------------

We simulate the process person by person, in the input order (arrival times non-decreasing).

Data structures:

- `finish_times[w]`: vector/list of all finish times of people who joined window `w` (0-based internally).
- For convenience, `arrival[i]`, `service[i]` arrays store each person’s input.

Algorithm for each person `i`:

1. Let `k = arrival[i]`, `t = service[i]`.

2. **Compute current queue length for each window at time `k`:**

   For each window `w` from `0` to `M-1`:

   ```text
   queue_count[w] = number of finish_times[w] entries > k
   ```

   Those with `finish <= k` have already left the queue, so are not counted.

3. **Choose window:**
   Find `best_window` such that:
   - `queue_count[best_window]` is minimal, and
   - if there are ties, choose the smallest index.

4. **Compute this person’s start and finish times at `best_window`:**

   - If `finish_times[best_window]` is empty:
     ```text
     start_time = k
     ```
   - Else:
     ```text
     last_finish = last element of finish_times[best_window]
     start_time = max(k, last_finish)
     ```

   Then:
   ```text
   end_time = start_time + t
   ```

5. Append `end_time` to `finish_times[best_window]`.

6. Output: window index in 1-based form and `end_time`:
   ```text
   best_window + 1, end_time
   ```

Complexity:

- Each of the `N` people:
  - For each of `M` windows, we may scan the list of finish times at that window. Total number of finish times across all windows is exactly `N`, and they are small.
- Worst case about `O(N^2)` operations (`≤ 10^4`), easily within time and memory limits.

This directly matches the problem rules, especially:
- People finishing at time `k` are not counted when a new person arrives at `k`, because we use `finish > k` to count.
- Service order at each window is FIFO with no overlaps by how we compute `start_time` with the last finish.


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, m;
vector<int> arrival, service;

void read() {
    cin >> n >> m;
    arrival.resize(n);
    service.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> arrival[i] >> service[i];
    }
}

void solve() {
    // We can directly implement this problem by simulation the queue process -
    // we just need to keep when everyone entered and then go in increasing
    // order of time. We don't actually need this, but we could use a priority
    // queue of "events" to make this more efficient.

    vector<vector<int>> finish_times(m);

    for(int i = 0; i < n; i++) {
        int k = arrival[i];
        int t = service[i];

        vector<int> queue_count(m, 0);
        for(int w = 0; w < m; w++) {
            for(int finish: finish_times[w]) {
                if(finish > k) {
                    queue_count[w]++;
                }
            }
        }

        int best_window = 0;
        for(int w = 1; w < m; w++) {
            if(queue_count[w] < queue_count[best_window]) {
                best_window = w;
            }
        }

        int start_time = k;
        if(!finish_times[best_window].empty()) {
            start_time = max(start_time, finish_times[best_window].back());
        }
        int end_time = start_time + t;

        finish_times[best_window].push_back(end_time);

        cout << (best_window + 1) << ' ' << end_time << '\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().strip().split()
    if not data:
        return

    it = iter(data)
    # Read N = number of people, M = number of windows
    N = int(next(it))
    M = int(next(it))

    # Read arrival and service times
    arrival = [0] * N
    service = [0] * N
    for i in range(N):
        arrival[i] = int(next(it))
        service[i] = int(next(it))

    # finish_times[w] holds the finish times of all people who chose window w
    finish_times = [[] for _ in range(M)]

    out_lines = []

    for i in range(N):
        k = arrival[i]  # arrival time of person i
        t = service[i]  # service time of person i

        # 1. Compute queue length at each window at time k
        queue_count = [0] * M
        for w in range(M):
            cnt = 0
            # Count people at window w whose finish time is > k
            for fin in finish_times[w]:
                if fin > k:
                    cnt += 1
            queue_count[w] = cnt

        # 2. Choose window with smallest queue length, tie -> smallest index
        best_window = 0
        for w in range(1, M):
            if queue_count[w] < queue_count[best_window]:
                best_window = w
            # If equal, keep existing best_window to preserve smallest index

        # 3. Compute start time at that window
        if finish_times[best_window]:
            last_finish = finish_times[best_window][-1]
            start_time = max(k, last_finish)
        else:
            start_time = k

        end_time = start_time + t

        # 4. Record and output
        finish_times[best_window].append(end_time)
        out_lines.append(f"{best_window + 1} {end_time}")

    sys.stdout.write("\n".join(out_lines))


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

This solution directly simulates the queues with simple lists, correctly handles the timing nuances, and runs easily within the given constraints.
