32223번 - 송도고 레일 정비 사업

송도고의 부지는 너무 커서, 큰 물건을 운반하기 까다롭다. 이를 해결하기 위해 진서는 송도고의 지하에 동서 방향으로 뻗어 있는 직선 레일들과 남북 방향으로 뻗어 있는 직선 레일들을 설치하였다. 하지만 공사 후에 설계도를 잃어버리는 바람에 어떤 레일의 시작점에 물건을 놓으면 최종적으로 어디에 운반되는지 알 수 없게 되었다. 다행히 진서는 운반 시설이 동서-레일 $n$개와 남북-레일 $m$개로 어떻게 이루어졌는지와 각 레일의 위치, 우선순위, 운반 방향을 기억하고 있다.

구체적으로, 각 $i$번 레일이 갖는 우선순위 $p_i$와 운반 방향 $d_i$가 주어진다. $1\le i\le n$이라면 해당 레일은 동서 방향으로 뻗어있고, $n+1\le i\le n+m$이라면 해당 레일은 남북 방향으로 뻗어있다. 레일의 우선순위 $p_i$는 $1$ 이상 $n+m$ 이하의 서로 다른 정수이다. 각각의 동서-레일은 모든 남북-레일과 교차하고, 각각의 남북-레일은 모든 동서-레일과 교차한다. 동서-레일끼리 교차하거나, 남북-레일끼리 교차하는 경우는 없다.

다음은 동서-레일의 정보이다.

• 동서-레일은 번호가 클수록 상대적으로 남쪽에 위치한다.
• $i$번의 동서-레일 위의 물건은 $d_i=1$이라면 서쪽으로 움직이고, $d_i=2$라면 동쪽으로 움직인다.
• $i$번의 동서-레일의 시작점은 $d_i=1$이라면 동쪽 끝, $d_i=2$라면 서쪽 끝이다.
• $i$번의 동서-레일 위에서 움직이던 물건은 우선순위 값이 더 작은, 즉 $p_i>p_j$인 $j$번의 남북-레일과의 교차점에 도달했을 때 그 즉시 $j$번의 남북-레일로 옮겨탄다.

다음은 남북-레일의 정보이다.

• 남북-레일은 번호가 클수록 상대적으로 동쪽에 위치한다.
• $i$번의 남북-레일 위의 물건은 $d_i=1$이라면 북쪽으로 움직이고, $d_i=2$라면 남쪽으로 움직인다.
• $i$번의 남북-레일의 시작점은 $d_i=1$이라면 남쪽 끝, $d_i=2$라면 북쪽 끝이다.
• $i$번의 남북-레일 위에서 움직이던 물건은 우선순위 값이 더 작은, 즉 $p_i>p_j$인 $j$번의 동서-레일과의 교차점에 도달했을 때 그 즉시 $j$번의 동서-레일로 옮겨탄다.

각 레일의 시작점에 물건을 놓았을 때 물건이 최종적으로 도착하는 레일의 번호를 구하자!

첫 번째 줄에는 두 정수 $n, m$이 공백으로 구분되어 주어진다.

이어서 $n+m$개의 각 $i+1$번째 줄에는 두 정수 $p_i,d_i$가 공백으로 구분되어 주어진다. $(1\le i\le n+m)$

$n+m$개의 각 $i$번째 줄에 $i$번 레일의 시작점에 물건을 놓았을 때 물건이 최종적으로 도착하는 레일의 번호를 출력한다.

• $1\le n,m\le 100\, 000$.
• $1\le p_i\le n+m$.
• $d_i\in\{1,2\}$.
• $p_i\neq p_j$ $(i\neq j)$.