The following test helped me a lot:

Input:
10 2
0
0
0
0
1 0
3 0
4 0
5 0
6 0
7 0
1 5
1 2 3 4 5
2 5
6 7 8 9 10

Output:
2 right
2 left
5 right
3 left
3 right
6 left
4 left
4 right
6 right
5 left