Estoques por faixa

Time limit: 3000 msMemory limit: 256 MB

Há $n$ depósitos em uma fila. Cada depósito $i$ armazena $m_i$ unidades de um produto de preço $p_i$ . Uma atualização substitui simultaneamente o preço e a quantidade de um depósito.

Uma consulta $(l,r,k)$ reúne as unidades existentes nos depósitos de $l$ até $r$ , ordena seus preços em ordem não decrescente, incluindo repetições, e pede o preço da unidade na posição $k$ , numerada a partir de 1.

Input

A primeira linha contém $n,q$ . Seguem $n$ linhas com $p_i,m_i$ e depois operações:

Output

Para cada consulta, imprima o preço pedido.

Samples

Sample 1

Input

Output

5
8

Antes da atualização, os preços ordenados são 1, 5, 5, 9, 9, 9.