분석해 보라

Paul Vitti는 뉴욕 마피아가 운영하는 유명한 카페 레스토랑 "The Godfather"의 주인이다. 단골 손님들은 매일 같은 시각에 카페를 찾는다. $i$번째 손님은 개점 후 $t_i$분에 가게에 들어온다.

매일 아침 Paul은 그날의 수프가 될 요리를 정한다. 수프가 아닐 때도 있다. $j$번째 날 요리 한 인분을 만드는 데 $D_j$분이 걸린다.

단골 손님들은 들어오자마자 그날의 수프를 한 인분씩 주문한다. 요리를 받은 손님은 그 자리에서 바로 먹고 자기 볼일을 보러 나간다. 주방에는 요리사와 가스레인지가 항상 충분하므로, 주문이 들어오면 곧바로 조리가 시작된다.

손님들은 모두 서로 알고 있어서 만나면 악수를 한다. 또한 들어오는 손님은 반드시 Paul과 악수해야 한다. 들어온 손님이 이미 요리를 기다리고 있는 다른 손님과 악수하면, 기다리던 손님은 시계를 보고, 그날 카페에서 이미 기다린 시간만큼 화가 난다. 아침에는 모두 기분이 좋아서 화남 정도는 0이다. 한 손님이 나가는 동시에 다른 손님이 들어와도 악수할 시간은 있다.

Paul은 손님들의 행동을 면밀히 분석한다. 각 날마다 악수 후 두 손님 중 한 명의 화남 정도가 그날 최대가 되는 두 손님을 찾아 달라. Paul은 이를 보고 더 빠른 요리사를 고용할지, 화난 손님을 내보낼지 정한다.

첫 줄에 손님 수 $n$ ($1 \le n \le 400000$)과 날 수 $m$ ($1 \le m \le 400000$)이 주어진다. 다음 줄에는 입장 시각 $t_i$ ($0 \le t_i < 400000$)가 $n$개 주어진다. 이어지는 $m$개 줄에는 각각 정수 $D_j$ ($0 \le D_j < 400000$)가 하나씩 주어지며, 이는 $j$번째 날 수프 한 인분을 조리하는 데 걸리는 시간이다.

각 날마다 두 정수 $i$와 $j$ ($0 \le i, j \le n$)를 출력한다. 두 번호는 악수가 둘 중 한 사람에게 마지막 악수가 될 수 있는 손님들의 번호이다. 손님 번호는 입력 순서대로 $1$부터 $n$까지이다. Paul의 번호는 $0$이며 화남 정도는 항상 0이니, 그를 화나게 하지 않는 편이 좋다.