송도고 레일 정비 사업

송도고의 부지는 너무 커서 큰 물건을 운반하기가 까다롭다. 이를 해결하기 위해 진서는 송도고 지하에 동서 방향으로 뻗은 직선 레일들과 남북 방향으로 뻗은 직선 레일들을 설치하였다. 하지만 공사 후에 설계도를 잃어버려서, 어떤 레일의 시작점에 물건을 놓으면 최종적으로 어디에 운반되는지 알 수 없게 되었다. 다행히 진서는 운반 시설이 동서 레일 $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\}$.
• $i \neq j$이면 $p_i \neq p_j$.