Алис Бобруу чухал мэссэж явуулахыг хүсч байна. $a = (a_{1}, ..., a_{n})$ мэссэж нь эерэг бүхэл тоонуудын (тэмдэгтүүдийн) дараалал байна.

Мэссэжийг шахахын тулд Алис хоёртын Хафмэн кодчилолыг ашиглахыг хүссэн. Бид хоёртын Хафмэн код эсвэл хоёртын угтвар кодыг $f$ функц болгоно. $f$ функц нь тэмдэгт мөр дахь үсэг бүрийг ялгаатай хоёр тэмдэгт $a_{i}$ ба $a_{j}$-н хувьд $f(a_{i})$ нь $f(a_{j})$-н угтвар биш байхаар (мөн эсрэгээрээ) хоёртын тэмдэгт мөррүү (буюу зөвхөн '$0$' ба '$1$' тэмдэгтүүдээс бүрдэх) хөрвүүлнэ. $a_{1}, a_{2}, ..., a_{n}$ мэссэжийн хөрвүүлэлтийн үр дүн нь тэмдэгт бүрийн хөрвүүлэлтийн хэлхээ байх буюу $f(a_{1})f(a_{2})... f(a_{n})$ тэмдэгт мөр байна. Хэрвээ $f$ функц өгөгдсөн тохиолдолд шахсан мэссэжийг хялбар бас давтагдахгүйгээр тайлах боломжтой учир Хафмэний кодууд маш хэрэгцээтэй. Кодыг сонгохдоо ихэвчлэн шахсан мэссэжийн нийт уртыг хамгийн бага байлгахаар сонгодог, өөрөөр $f(a_{1})f(a_{2})... f(a_{n})$ тэмдэгт мөрийн урт.

Аюулгүй байдлын үүднээс Алис бүх мэссэжийг явуулахыг хүссэнгүй. Түүний оронд тэр мэссэжийн дэд тэмдэгт мөрүүдийг авч тэдгээрийг тус тусад нь явуулахыг хүссэн. Өгөгдсөн $a_{l_{i}}... a_{r_{i}}$ дэд тэмдэгт мөр бүрийн хувьд тэр Хафмэн кодчилолын хамгийн бага уртыг мэдэхийг хүсч байна.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх буюу анхны мэссэжийн урт юм. Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 100 000$) байх буюу мэссэжийн тэмдэгтүүд юм.

Дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 100 000$) байх ба асуулгуудын тоо юм.

Дараагийн $q$ мөрөнд асуулгуудын тайлбар байна. Эдгээрийн $i$-р мөрөнд хоёр бүхэл тоон утга $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) байх буюу $i$-р дэд тэмдэгт мөрийн зүүн болон баруун төгсгөлүүдийн байрлал байна. Байрлалууд $1$-с эхлэн дугаарлагдана. Дэд тэмдэгт мөрүүд ямар ч тохиолдлоор давхардаж болно. Оролтонд ижил дэд тэмдэгт мөрүүд нэгээс олон байж болно.

Гаралт

Гаралтанд $q$ мөр хэвлэнэ. Мөр бүрт $a_{l_{i}}... a_{r_{i}}$ дэд тэмдэгт мөрийн Хафмэн хөрвүүлэлтийн боломжит хамгийн бага урт байна.

Эхний асуулга дээр дэд тэмдэгт мөрийг хөрвүүлэх тохиромжтой замуудын нэг нь $1$-г "$0$", $2$-г "$10$", $3$-г "$11$" болгож хөрвүүлэх юм.

Үсгийг хоосон дэд тэмдэгт мөррүү хөрвүүлэх нь зөв (тавдугаар асуулга дээрх шиг).