#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

struct katapult
{
  int levy;
  int pravy;
  int umisteni;
  int index;

  katapult(int l, int p, int i) {
    levy = l;
    pravy = p;
    index = i;
    umisteni = -1;
  }

  bool operator < (const katapult& k) const {
    return (this->levy < k.levy);
  }

  bool operator > (const katapult& k) const {
    return (this->pravy > k.pravy);
  }
};

int main() {
  using namespace std;
  ios_base::sync_with_stdio(false);

  int n, k;
  vector<katapult> katapulty;

  priority_queue<katapult, vector<katapult>, greater<katapult> > halda_k;
  priority_queue<int, vector<int>, greater<int> > halda_u;

  cin >> n >> k;

  for (int i=0; i<k; ++i) {
    int l, r;
    cin >> l >> r;
    katapulty.push_back(katapult(l, r, i));
    halda_u.push(katapulty[i].levy);
  }

  sort(katapulty.begin(), katapulty.end());

  int akt = 0; int i=0;
  while (1) {
    while (i < k && katapulty[i].levy <= akt) {
      halda_k.push(katapulty[i]);
      halda_u.push(katapulty[i].pravy);
      ++i;
    }

    if (!halda_k.empty()) {
      struct katapult nejmensi = halda_k.top();
      halda_k.pop();
      if (nejmensi.pravy < akt) {
        cout << "Katapulty nelze rozmístit" << endl;
        break;
      }

      katapulty[nejmensi.index].umisteni = akt;
    }

    if (!halda_k.empty()) {
      akt++;
    }
    else {
      if (!halda_u.empty()) {
        int n_akt = akt;
        while (halda_u.size() && n_akt <= akt) {
          n_akt = halda_u.top();
          halda_u.pop();
        }
        akt = n_akt;
      }
      else {
        break;
      }
    }
  }

  for (int i=0; i<k; i++) {
    cout << "Katapult " << katapulty[i].index << " je na poli " << katapulty[i].umisteni << endl;
  }
}