Az első sor két egész számot tartalmaz, $n$, $q$ ($1 \le n, q \le 2 \cdot 10^5$) --- a tömb elemeinek száma és a lekérdezések száma.

A második sor $n$ egész számot tartalmaz, $a_i$ ($1 \le a_i \le 6 \cdot 10^6$) --- a tömb leírása.

Minden következő $q$ sor két egész számot tartalmaz, $l$, $r$ ($1 \le l \le r \le n$) --- a lekérdezések leírása.