Bibble və Kapitan Snappy#4486
Bibble və Kapitan Snappy nə ilə məşğul olacaqlarını bilməyəndə, müxtəlif maraqlı oyunlar oynayırlar. Bu gün Kapitan Snappy Bibble-in riyaziyyatı daha yaxşı mənimsəməsinə kömək edəcəyini düşündüyü yeni bir oyun icad edib.
Oyunun qaydaları sadədir: Kapitan Snappy sayda lövhə götürür, onları -dən -ə qədər nömrələyir və üzərinə bəzi rəqəmlər yazır. Sonra o, və adlı iki rəqəm söyləyir və Bibble -dən -ə qədər nömrələri olan lövhələrdəki bütün rəqəmlərin cəmini hesablamalıdır.
Bibble bütün mümkün cavabları əzbərləməsin deyə, Kapitan Snappy bəzən rəqəmlərin dəyərlərini dəyişir. Xüsusilə, o, [l, r] aralığındakı bütün rəqəmləri dəyişir, bu lövhələrə ardıcıllıqla -dən r - l + 1-ə qədər olan rəqəmləri artan qaydada yazır.
Bibble hələ yaxşı hesablamır, ona görə də sizdən proqram yazmağı xahiş edir ki, bu onun üçün hesablamaları yerinə yetirsin.
Birinci sətirdə rəqəmi (1 \le n \le 10^6) — lövhələrin sayı verilir.
İkinci sətirdə lövhələr üzərində yazılmış başlanğıc dəyərləri göstərən rəqəm verilir (hər bir rəqəm 10^9-dən böyük deyil).
Daha sonra rəqəmi (1 \le m \le 10^5) — sorğuların sayı verilir.
Daha sonra sətir, hər biri iki növ sorğudan birini təsvir edən sətir gəlir. Sətirin ilk rəqəmi sorğunun növünü t~(1 \le t \le 2) göstərir.
Əgər t = 1, bu halda ardınca iki rəqəm və izləyir. Bu halda lövhələrdəki -dən -ə qədər olan nömrələrdə bütün rəqəmlərin cəmini hesablamaq lazımdır.
Əgər t = 2, bu halda ardınca iki rəqəm və izləyir. Bu halda lövhələrdəki -dən -ə qədər olan nömrələrdə bütün rəqəmlər ardıcıllıqlə 1, 2, ... , r - l + 1 ilə əvəz olunur.
Bütün sorğuların düzgün şəkildə verildiyi və lövhələrin nömrələnməsinin birlə başladığı təmin edilir.
Hər bir növ sorğu üçün nəticəni — verilmiş aralıqda [l, r] olan lövhələrin dəyərlər cəmini bir rəqəm şəklində çıxış edin.
Nümunə 1