Giải bài trực tuyến

Vào năm 2011 người ta phát minh ra tàu siêu tốc có thể chứa rất nhiều người. Tuyến đường mà tàu đi sẽ có N ga được đánh số từ 0 đến N-1. Trên tàu có K chỗ ngồi.

Trung tâm quản lí tàu nhận được M yêu cầu từ khách hàng và trung tâm đó sẽ phải đáp ứng M yêu cầu đó theo thứ tự nhập vào.

Vé sẽ được bán cho khách hàng nếu trên đoạn đường mà khách hàng đó yêu cầu có ghế còn trống. Khi khách xuống tại một ga nào đó, ghế của người đó sẽ được coi là ghế trống kể từ ga đó và có thể bán cho người có nhu cầu đi. Với mỗi khách hàng ta được biết X và Y là ga lên và ga xuống của hành khách đó.

_ Nếu yêu cầu của hành khách được đáp ứng, trung tâm sẽ thông báo 1.

_ Ngược lại nếu yêu cầu của hành khách không thể đáp ứng, trung tâm sẽ thông báo 0.

Input

_ Dòng đầu tiên chứa 3 số nguyên N,K,M

_ M dòng sau mỗi dòng chứa 2 số nguyên X và Y

_ Giới hạn: 1<=N,K<=100000, 1<=M<=500000, 0<=X<Y<=N-1

Output

_ Gồm M dòng ứng với M yêu cầu của khách hàng, dòng thứ i in ra 1 nếu yêu cầu thứ i được đáp ứng ngược lại in ra 0.

Ví dụ

Input:

5 1 4
0 1
1 2
2 4
2 3
Output:
1
1
1
0