# Rikka with sequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta have a sequence. Because the sequence is very self-willed(RenXing), at first the sequence is empty. And then Yuta do n operations on this sequence, each operation is either of these two types:

1.Add a number w into each gap of the sequence. For example if w=3 and the sequence before is “2 4”, it will be changed to “3 2 3 4 3”.
**after the first operation of the first type, there is only one number in the sequence**

2.Query the kth small number in the subsequence [L,R]. For example if k=2, L=2, R=4 and the sequence is “3 2 3 4 2”, the answer will be 3.

Yuta wants Rikka to tell him the answer of each query.

It is too difficult for Rikka. Can you help her?

## Input

The first line contains one number $n(n \leq 100000)$. Each of the following $n$ lines describes an operation: if it is “1 w” it will be the first type. Otherwise if it is “2 L R k”, it will be the second type. $(1 \leq w \leq 10^{9}, L \leq R \leq 10^{18})$
R will not be larger than the length of the sequence

## Output

For each query operation, output one number – the answer.

## Sample Input

6
1 3
1 1
2 2 3 2
1 2
2 3 5 2
2 1 4 4

## Sample Output

3
2
3

hujie

## Source

BestCoder Round #37 (\$)