Çeburaşka və timsah Gena

Çeburaşka və timsah Gena boş vaxtlarında müxtəlif maraqlı oyunlar oynayırlar. Bu gün Gena, Çeburaşkanın arifmetikanı öyrənməsinə kömək edəcəyini düşündüyü yeni bir oyun icad etdi. Oyunun qaydaları çox sadədir: Gena $n$ taxta götürəcək, onları $1$-dən $n$-ə qədər nömrələyəcək və üzərinə bəzi rəqəmlər yazacaq. Sonra o, iki rəqəm $l$ və $r$ deyəcək və Çeburaşka $l$-dən $r$-ə qədər nömrələnmiş taxtaların üzərindəki bütün rəqəmlərin cəmini hesablamalıdır.

Bununla yanaşı, Çeburaşka bütün mümkün cavabları öyrənməsin deyə, Gena bəzən bəzi rəqəmləri başqaları ilə dəyişir, yəni $[l,r]$ intervalındakı bütün rəqəmləri. O, çox düşünmək istəmir, ona görə də sadəcə bu taxtaların üzərinə $1$-dən $r-l+1$-ə qədər olan rəqəmləri ardıcıl yazır. Çeburaşka hələ arifmetikanı yaxşı bilmir, ona görə də sizdən ona bu işdə kömək edəcək bir proqram yazmağı xahiş edir.

Giriş verilənləri

Birinci sətirdə bir ədəd $n(1\le n\le 10^6)$ — taxtaların sayı verilir. Növbəti sətirdə taxtaların üzərində yazılmış başlanğıc dəyərlər olan $n$ ədəd verilir (bütün ədədlər $10^9$-u keçmir). Daha sonra $m(1\le m\le 10^5)$ — sorğuların sayı verilir. Sonra $m$ sətir gəlir, sətirdəki ilk ədəd sorğunun növü $t(1\le t\le 2)$-dir.

• Əgər $t=1$-dirsə, sonra iki ədəd $l$ və $r$ gəlir. Siz $l$-dən $r$-ə qədər nömrələnmiş taxtaların üzərindəki bütün rəqəmlərin cəmini hesablamalısınız;

• Əgər $t=2$-dirsə, sonra iki ədəd $l$ və $r$ gəlir. Bu o deməkdir ki, $l$-dən $r$-ə qədər nömrələnmiş taxtaların üzərində indi müvafiq olaraq $1$-dən $r-l+1$-ə qədər olan rəqəmlər olacaq.

Bütün intervalların düzgün olduğu təmin edilir. Taxtaların nömrələnməsi birlə başlayır.

Çıxış verilənləri

Hər bir $1$ nömrəli sorğu üçün $[l,r]$ intervalındakı rəqəmlərin cəmini çıxarın.

Nümunələr