We have got N number, from 1 to N. There are 2 types of query:

1. move number from index i to index j
2. write what number is at index i

ex.

(0,1,2,3,4);

2 ? -> 2

(0,1,3,4,2); <- from 2 to 4

(0,4,1,3,2); <- from 3 to 1

3 ? -> 3

4 ? -> 2

(0,4,1,3,2); <- from 1 to 1

0 ? -> 0

1 ? -> 4

2 < N < 10 000 000 M < 500 000

I tried with the sqrt-decomposition but not fast enough.. any ideas?