#include <stdio.h>
#include <stdlib.h>

/**
 * Vzorový program pro 28-3-4 Katapulty
 * Předpokládaný formát vstupu:
 *   na prvním řádku dvě čísla N, K
 *      (N je délka lajny, K je počet katapultů)
 *   na každém z následujících K řádků dvě čísla L_i, P_i
 *      udávající levý a pravý okraj úseku i-tého katapultu (hranice úseků jsou včetně)
 *
 * Program katapulty setřídí podle levého okraje a naplánuje události odpovídající všem
 * začátkům. V hlavní smyčce se vždy přidají katapulty, jejichž úsek již začal a vybere
 * se katapult s nejmenším pravým okrajem. Pokud je možné ho umístit, katapult se umístí
 * a naplánuje se další zastavení (sousední políčko nebo nejbližší příští událost).
**/

#define MAX_K 1000000

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

struct katapult **halda_k;
int halda_k_velikost = 0;
int halda_u[2*MAX_K+1];
int halda_u_velikost = 0;

int cmp_katapulty(const void *a, const void *b) {
  struct katapult *ka = (struct katapult *) a;
  struct katapult *kb = (struct katapult *) b;

  if (ka->levy < kb->levy)
    return -1;
  else
    return 1;
}

void katapult_dolu(int i) {
  while (i*2 < halda_k_velikost &&
         (halda_k[i]->pravy >= halda_k[2*i]->pravy ||
         (halda_k_velikost >= 2*i+1 && halda_k[i]->pravy >= halda_k[2*i+1]->pravy))) {
    int ni = (halda_k[2*i]->pravy > halda_k[2*i+1]->pravy ? 2*i+1 : 2*i);
    struct katapult *tmp = halda_k[i];
    halda_k[i] = halda_k[ni];
    halda_k[ni] = tmp;
    i = ni;
  }
}

void katapult_nahoru(int i) {
if (i > 1)
  while (i > 1 && halda_k[i]->pravy < halda_k[i/2]->pravy) {
    struct katapult *tmp = halda_k[i];
    halda_k[i] = halda_k[i/2];
    halda_k[i/2] = tmp;
    i = i/2;
  }
}

void pridej_katapult(struct katapult *katapult) {
  halda_k[++halda_k_velikost] = katapult;
  katapult_nahoru(halda_k_velikost);
}

struct katapult * min_katapult() {
  struct katapult *tmp = halda_k[1];
  halda_k[1] = halda_k[halda_k_velikost--];
  katapult_dolu(1);
  return tmp;
}

void udalost_dolu(int i) {
  while (i*2 <= halda_u_velikost &&
         (halda_u[i] >= halda_u[2*i] ||
         (halda_u_velikost >= 2*i+1 && halda_u[i] >= halda_u[2*i+1]))) {
    int ni = (halda_u[2*i] > halda_u[2*i+1] ? 2*i+1 : 2*i);
    int tmp = halda_u[i];
    halda_u[i] = halda_u[ni];
    halda_u[ni] = tmp;
    i = ni;
  }
}

void udalost_nahoru(int i) {
  while (i > 1 && halda_u[i] < halda_u[i/2]) {
    int tmp = halda_u[i];
    halda_u[i] = halda_u[i/2];
    halda_u[i/2] = tmp;
    i = i/2;
  }
}

void pridej_udalost(int udalost) {
  halda_u[++halda_u_velikost] = udalost;
  udalost_nahoru(halda_u_velikost);
}

int min_udalost() {
  int tmp = halda_u[1];
  halda_u[1] = halda_u[halda_u_velikost--];
  udalost_dolu(1);
  return tmp;
}

int main(void) {
  int k, n;

  scanf("%d", &n);
  scanf("%d", &k);

  halda_k = malloc(k*sizeof(struct katapult *));

  struct katapult *katapulty = malloc(k * sizeof(struct katapult));

  for (int i=0; i<k; i++) {
    katapulty[i].index = i;
    katapulty[i].umisteni = -1;
    scanf("%d %d", &(katapulty[i].levy), &(katapulty[i].pravy));
    pridej_udalost(katapulty[i].levy);
  }

  qsort(katapulty, k, sizeof(struct katapult), cmp_katapulty);

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

    if (halda_k_velikost > 0) {
      struct katapult *nejmensi = min_katapult();
      if (nejmensi->pravy < akt) {
        printf("Katapulty nelze rozmístit");
        break;
      }

      nejmensi->umisteni = akt;
    }

    if (halda_k_velikost > 0) {
      akt++;
    }
    else {
      if (halda_u_velikost) {
        int n_akt = akt;
        while (halda_u_velikost && n_akt <= akt) {
          n_akt = min_udalost();
        }
        akt = n_akt;
      }
      else {
        break;
      }
    }
  }

  for (int i=0; i<k; i++) {
    printf("Katapult %d je na poli %d\n", katapulty[i].index, katapulty[i].umisteni);
  }
}