Có ~n~ con khỉ đang treo mình trên ~1~ cái cây rất cao. Những con khỉ được đánh số từ ~1~ đến ~n~. Con khỉ đầu đàn được đánh số là ~1~ và hiện tại nó đang treo mình trên cây bằng cách sử dụng đuôi của nó. ~1~ con khỉ có ~2~ tay và nó có thể dùng mỗi tay để bám vào đuôi của ~1~ con khỉ (có thể tự bám vào đuôi của chính nó). Mỗi tay chỉ có thể bám được nhiều nhất ~1~ đuôi nhưng mỗi cái đuôi có thể được bám bởi nhiều tay khác nhau. Trong ~m~ giây sắp tới (từ giây thứ ~0~ đến giây thứ ~m-1~) mỗi giây sẽ có ~1~ con khỉ buông ~1~ tay của nó. Việc của bạn là với mỗi con khỉ hãy tính thời điểm mà nó bị rơi khỏi cây.

Input

Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~m~ ~(1 \le n \le 2\cdot10^5, 1 \le m \le 4\cdot10^5)~ với ~n~ là số con khỉ và ~m~ là số giây mà ta sẽ quan tâm.

~n~ dòng tiếp theo chứa ~2~ số nguyên dương ~l_i, r_i~. ~l_i~ sẽ có giá trị là ~-1~ hoặc chỉ số của con khỉ mà tay trái của con khỉ thứ ~i~ đang nắm đuôi. Tương tự với ~r_i~ sẽ có giá trị là ~-1~ hoặc chỉ số của con khỉ mà tay phải của con khỉ thứ ~i~ đang nắm đuôi. Giá trị ~-1~ tức là tay của con khỉ thứ ~i~ hiện đang không nắm đuôi con khỉ nào. Con khỉ đầu đàn (con khỉ mang số thứ tự ~1~) thì dùng đuôi của nó để bám vào cành cây.

~m~ dòng tiếp theo mô tả sự kiện sẽ diễn ra trong ~m~ giây từ ~0~ đến ~m-1~. Dòng thứ ~j~ sẽ gồm ~2~ chỉ số ~p_j~ và ~h_j~ ám chỉ việc ~1~ con khỉ sẽ buông tay. ~p_j~ là chỉ số của con khỉ buông tay ~(1 \le p_j \le n)~ và ~h_j~ sẽ mang giá trị ~1~ nếu con khỉ ~p_j~ buông tay trái hoặc mang giá trị ~2~ nếu con khỉ ~p_j~ buông tay phải.

Dữ liệu luôn đảm bảo con khỉ sẽ không buông tay nếu tại thời điểm truy vấn nó không nắm cái đuôi nào. Các con khỉ có thể dùng cả ~2~ tay để nằm đuổi của cùng ~1~ con khỉ và cũng có thể dùng tay để tự nắm đuôi của chính nó.

Output

In ra ~n~ dòng. Dòng thứ ~i~ là thời điểm mà con khỉ thứ ~i~ bắt đầu rơi từ trên cây xuống. Nếu con khỉ không bao giờ rơi xuống thì in ra ~-1~.

Scoring

Sample Input 1

3 2
-1 3
3 -1
1 2
1 2
3 1

Sample Output 1

-1
1
1

Sample Input 2

4 5
2 2
3 -1
4 -1
-1 2
1 1
2 1
3 1
1 2
4 2

Sample Output 2

-1
3
2
3