카드 수집

JOI-kun은 카드 게임에서 카드 모으기를 좋아한다. 각 카드에는 힘(strength)과 비용(cost)을 나타내는 정수가 두 개씩 있다. 새 카드를 얻기 위해 JOI-kun은 카드 교환소에 카드 $N$장을 가져간다. 카드에는 1번부터 $N$번까지 번호가 붙어 있다. 카드 $i$의 힘은 $S_i$이고, 비용은 $V_i$이다.

교환소에는 기계가 두 대 있다. 카드 A와 B를 첫 번째 기계에 넣으면, 힘이 A와 B의 힘 중 최댓값과 같고 비용이 A와 B의 비용 중 최댓값과 같은 카드 C를 받을 수 있다. 두 번째 기계도 같은 방식으로 동작하지만, 최댓값 대신 최솟값을 사용한다.

JOI-kun은 기계를 정확히 $N-1$번 사용해 새 카드를 얻는다. 카드 $N$장을 1번부터 $N$번까지 일렬로 세운다. 그다음 다음 작업을 $N-1$번 반복한다. 인접한 카드 두 장을 고르고, 기계 하나로 새 카드와 교환한 뒤, 새 카드를 고른 두 카드가 있던 자리에 놓는다.

$N-1$번의 작업이 끝나면 카드 한 장이 남는다. 목표 카드 $M$장의 목록 $(T_j, W_j)$가 주어졌을 때, JOI-kun이 얻을 수 있는 카드를 목록에서 모두 찾아라.

첫 줄에 $N$과 $M$이 주어진다. 다음 $N$줄에는 카드 $i$의 $S_i$와 $V_i$가 주어진다. 이어지는 $M$줄에는 $j$번째 목표 카드의 $T_j$와 $W_j$가 주어진다.

JOI-kun이 얻을 수 있는 목표 카드의 번호를 오름차순으로 한 줄에 출력한다.

• $2 \le N \le 200000$
• $1 \le M \le 200000$
• 모든 $i$에 대해 $1 \le S_i \le 10^9$
• 모든 $i$에 대해 $1 \le V_i \le 10^9$
• 모든 $j$에 대해 $1 \le T_j \le 10^9$
• 모든 $j$에 대해 $1 \le W_j \le 10^9$
• 주어지는 값은 모두 정수이다.