전우

전투 상황에서 병사들이 일렬로 서 있고, 왼쪽부터 오른쪽으로 $1$번부터 $S$번까지 번호가 매겨져 있다. 각 병사는 자기 자신을 지키고 적을 공격하는 것 외에도, 바로 양옆(왼쪽과 오른쪽)에 있는 가장 가까운 두 이웃을 함께 지켜야 한다. 이 두 이웃을 그 병사의 "전우(buddy)"라고 부른다. 단, 가장 왼쪽 병사에게는 왼쪽 전우가 없고, 가장 오른쪽 병사에게는 오른쪽 전우가 없다.

어떤 병사의 왼쪽 또는 오른쪽 전우가 전사하면, 그 방향에서 살아 있는 가장 가까운 다음 병사가 새로운 전우가 된다.

전투가 격렬해지면서 여러 병사가 전사한다. 전사 보고가 들어올 때마다 군 정보 시스템은 새로 맺어진 전우 관계를 병사들에게 알려야 한다. 각 전사 보고는 방금 전사한 연속된 병사 구간을 나타낸다.

각 전사 보고에 대해, 그 구간을 대열에서 제거했을 때 새로 맺어지는 전우를 출력하는 프로그램을 작성하라. 즉, 제거된 구간의 바로 왼쪽에서 살아남은 첫 병사와, 바로 오른쪽에서 살아남은 첫 병사를 구하면 된다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 대열의 병사 수 $S$와 전사 보고의 수 $B$가 주어진다 ($1 \le B \le S \le 10^5$). 병사는 대열에서의 위치에 따라 $1$번부터 $S$번까지 번호가 매겨지며, $1$번이 가장 왼쪽, $S$번이 가장 오른쪽 병사이다.

이어지는 $B$개의 줄에는 각각 전사 보고가 두 정수 $L$과 $R$로 주어진다 ($1 \le L \le R \le S$). 이는 $L$번부터 $R$번까지의 병사가 방금 전사했음을 뜻한다. 이 보고 시점까지 해당 병사들은 모두 살아 있었다고 가정해도 된다.

마지막 테스트 케이스 다음에는 두 개의 $0$이 적힌 줄이 주어진다.

각 테스트 케이스에 대해 $B+1$개의 줄을 출력한다.

$i$번째 줄에는 $i$번째 전사 보고 L R에 따라 병사들을 제거한 뒤 새로 맺어지는 전우를 출력한다. 즉, $L$의 왼쪽에서 살아남은 첫 병사와 $R$의 오른쪽에서 살아남은 첫 병사를 한 칸 공백으로 구분하여 출력한다. 어느 방향에도 살아남은 병사가 없으면 그 자리에는 별표 *를 출력한다.

각 테스트 케이스의 출력 뒤에는 하이픈 - 하나만 있는 줄을 출력한다.