Bit alt-seqmentinin istisna edilməsi

Giriş

Birinci sətirdə bir tam ədəd $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test hallarının sayı verilir.

Hər test halının birinci sətrində iki tam ədəd $n$ və $q$ ( $1 \leq n, q \leq 2 \cdot 1 0^{5}$ 1 \le n, q \le 2 \cdot 10^5) — binar massivin uzunluğu və sorğuların sayı verilir.

Hər test halının ikinci sətrində boşluqla ayrılmış $n$ tam ədəd $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $a_{i} \in {0, 1}$ a_i \in \{0, 1\}) — massivin elementləri verilir.

Sonrakı $q$ sətir sorğuları təsvir edir. Hər sətirdə iki tam ədəd $l$ və $r$ ( $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) — sorğu aralığının sərhədləri verilir.

Bütün test halları üzrə həm $n$ -lərin cəminin, həm də $q$ -ların cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i aşmadığı təmin edilir.

Çıxış

Hər sorğu üçün ayrıca sətirdə bir tam ədəd — $a [l \dots r]$ a[l \dots r] alt massivində ardıcıl alt-seqment kimi rast gəlinməyən binar ardıcıllığın minimal ədədi qiymətini $998244353$ moduluna görə çıxarın.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci test halında massiv $a = [0, 1, 0]$ a = [0, 1, 0]-dır.

Birinci $[1, 3]$ sorğusunda mövcud olan ardıcıl alt-seqmentlər bunlardır: $[0], [1], [0, 1], [1, 0]$ [0], [1], [0, 1], [1, 0] və $[0, 1, 0]$ [0, 1, 0]. Onların uyğun onluq qiymətləri $2, 3, 5, 6$ 2, 3, 5, 6 və $10$ -dur. Yaranmayan ən kiçik qiymət $4$ -dür ki, bu da $[0, 0]$ ardıcıllığına uyğun gəlir.
İkinci $[1, 2]$ sorğusunda alt massiv $[0, 1]$ -dir. Mövcud alt-seqmentlər: $[0], [1]$ və $[0, 1]$ . Ən kiçik çatışmayan qiymət yenə $4$ -dür ( $[0, 0]$ ardıcıllığı).
Üçüncü $[2, 2]$ sorğusunda alt massiv $[1]$ -dir. Yeganə mövcud alt-seqment $[1]$ -dir (qiyməti $3$ ). Ən kiçik çatışmayan qiymət $2$ -dir ( $[0]$ ardıcıllığı).

İkinci test halında massiv $a = [1, 1, 1, 1]$ a = [1, 1, 1, 1]-dir. $[1, 4]$ sorğusu üçün $[0]$ ardıcıllığına (qiyməti $2$ ) heç vaxt rast gəlinmir, ona görə də cavab $2$ -dir.

Üçüncü test halında massiv $a = [1, 0, 0, 1]$ a = [1, 0, 0, 1]-dir.

$[1, 3]$ sorğusu üçün alt massiv $[1, 0, 0]$ [1, 0, 0]-dır. O, $[0], [1], [0, 0], [1, 0]$ [0], [1], [0, 0], [1, 0] alt-seqmentlərini (qiymətləri $2, 3, 4, 6$ 2, 3, 4, 6) ehtiva edir. Ən kiçik çatışmayan qiymət $5$ -dir ( $[0, 1]$ ardıcıllığı).
$[2, 4]$ sorğusu üçün alt massiv $[0, 0, 1]$ [0, 0, 1]-dir. O, $[0], [1], [0, 0], [0, 1]$ [0], [1], [0, 0], [0, 1] alt-seqmentlərini (qiymətləri $2, 3, 4, 5$ 2, 3, 4, 5) ehtiva edir. Ən kiçik çatışmayan qiymət $6$ -dır ( $[1, 0]$ ardıcıllığı).
$[1, 4]$ sorğusu üçün alt massiv $2, 3, 4, 5$ 2, 3, 4, 5 və $6$ qiymətlərini ehtiva edir. Ən kiçik çatışmayan qiymət $7$ -dir ( $[1, 1]$ ardıcıllığı).

Bal hesablama

Alt məsələ 1 (100 bal): $\sum n \leq 2000$ \sum n \le 2000 və $\sum q \leq 2000$ \sum q \le 2000.
Alt məsələ 2 (150 bal): $\sum n \leq 40000$ \sum n \le 40000 və $\sum q \leq 40000$ \sum q \le 40000.
Alt məsələ 3 (250 bal): Əlavə məhdudiyyət yoxdur.