So this question is interesting. I was updating too much and was getting TLE. Once a buddy dies, there are obviously no more requests containing army members who are no more. We can therefore safely update only the end points of every given query.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * 
 * @author Sanchit M. Bhatnagar
 * @see http://uhunt.felix-halim.net/id/74004
 * 
 */
public class P12356 {

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out = new PrintWriter(System.out);
    StringTokenizer st = null;

    String line = null;
    while ((line = br.readLine()) != null) {
      st = new StringTokenizer(line);
      int S = Integer.parseInt(st.nextToken());
      int B = Integer.parseInt(st.nextToken());
      if (S == 0 && B == 0)
        break;
      int[] leftBuddy = new int[S + 2];
      int[] rightBuddy = new int[S + 2];
      for (int i = 1; i <= S; i++) {
        leftBuddy[i] = i - 1;
        rightBuddy[i] = i + 1;
      }
      rightBuddy[S] = 0;
      for (int i = 0; i < B; i++) {
        st = new StringTokenizer(br.readLine());
        int l = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        if (leftBuddy[l] == 0)
          out.print("* ");
        else
          out.print(leftBuddy[l] + " ");
        if (rightBuddy[r] == 0)
          out.println("*");
        else
          out.println(rightBuddy[r]);
        leftBuddy[rightBuddy[r]] = leftBuddy[l];
        rightBuddy[leftBuddy[l]] = rightBuddy[r];
      }
      out.println("-");
    }
    out.close();
    br.close();
  }
}