There is a vector of intervals (called v) that is initially empty. There are Q queries to process. two types of queries might appear:

1. add an interval (x, y) to an arbitrary place in v. (1 <= x <= y <= 10 ^ 5)

2. What is the last interval among the first t elements in v, that contains the number x. (1 <= t <= 10 ^ 9)

the number of queries is at most 10 ^ 5