Alt sayı

Petrik və Vasilko əsl dostdurlar və bir-birlərinə daim maraqlı məsələlər verirlər. Lakin Vasilko həmişə dostunun məsələlərini asanlıqla həll edir, buna görə də Petrik ona həqiqətən çətin bir məsələ verməyə qərar verdi. Budur, onun tapdığı məsələ.

Bir B ədədini A ədədinin alt ədədi adlandırırıq, əgər A ədədindən bəzi rəqəmləri silməklə qalan rəqəmlər B ədədini təşkil edirsə.

N rəqəmli X ədədi verilir. X[K] olaraq X ədədinin ən böyük K rəqəmli alt ədədini təyin edək. M sorğuya cavab vermək lazımdır. Hər bir sorğu iki ədəddən ibarətdir — K və L. Sorğunun cavabı X[K] ədədinin L-ci rəqəmidir.

Bu məsələ Vasilkoya həqiqətən düşündürdü. Bəs siz onu daha sürətli həll edə bilərsinizmi?

Tapşırıq

Verilmiş ədəd və sorğular ardıcıllığına görə lazım olan rəqəmləri tapacaq bir proqram yazın.

Giriş məlumatları

Girişin birinci sətirində uzunluğu N olan X tam ədədi verilir (1 ≤ N ≤ 10^5). İkinci sətirdə M ədədi verilir (1 ≤ M ≤ 10^5). Sonrakı M sətirdə hər biri iki ədəddən ibarət olan K[i], L[i] (1 ≤ K[i] ≤ N, 1 ≤ L[i] ≤ K[i]) — i-ci sorğunun parametrləri verilir.

Çıxış məlumatları

Çıxış uzunluğu 'M' olan bir sətir olmalıdır, burada 'i-ci' simvol 'i-ci' sorğunun cavabıdır.

Nümunələr

Qiymətləndirmə

Test dəsti 3 blokdan ibarətdir, hansılar üçün əlavə olaraq belə şərtlər yerinə yetirilir:

1. 15 % bal: N = 20, M = 10000.

2. 25 % bal: N×M ≤ 500000.

3. 60 % bal: N ≤ 100000, M ≤ 50000.