Bitsel Alt Parça Hariç Tutma

Giriş

İlk satır tek bir tam sayı $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) içerir — test durumlarının sayısı.

Her test durumunun ilk satırı iki tam sayı $n$ ve $q$ ( $1 \leq n, q \leq 2 \cdot 1 0^{5}$ 1 \le n, q \le 2 \cdot 10^5) içerir — ikili dizinin uzunluğu ve sorguların sayısı.

Her test durumunun ikinci satırı boşluklarla ayrılmış $n$ tam sayı $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $a_{i} \in {0, 1}$ a_i \in \{0, 1\}) içerir — dizinin elemanları.

Sonraki $q$ satır sorguları açıklar. Her satır iki tam sayı $l$ ve $r$ ( $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) içerir — sorgu aralığının sınırları.

Tüm test durumları boyunca hem $n$ değerlerinin toplamının hem de $q$ değerlerinin toplamının $2 \cdot 1 0^{5}$ 2 \cdot 10^5 değerini aşmadığı garanti edilir.

Çıktı

Her sorgu için yeni bir satırda tek bir tam sayı yazdırın — $a [l \dots r]$ a[l \dots r] içinde ardışık bir alt parça olarak bulunmayan bir ikili dizinin en küçük sayısal değeri, $998244353$ modülüne göre.

Örnekler

Örnek 1

Loading

Not

İlk test durumunda dizi $a = [0, 1, 0]$ a = [0, 1, 0] şeklindedir.

Birinci sorguda $[1, 3]$ , mevcut ardışık alt parçalar $[0], [1], [0, 1], [1, 0]$ [0], [1], [0, 1], [1, 0] ve $[0, 1, 0]$ [0, 1, 0] şeklindedir. Bunların ondalık değerleri sırasıyla $2, 3, 5, 6$ 2, 3, 5, 6 ve $10$ 'dur. Oluşturulmayan en küçük değer $4$ 'tür ve bu da $[0, 0]$ dizisine karşılık gelir.
İkinci sorguda $[1, 2]$ , alt dizi $[0, 1]$ 'dir. Mevcut alt parçalar $[0], [1]$ ve $[0, 1]$ 'dir. En küçük eksik değer yine $4$ 'tür ( $[0, 0]$ dizisi).
Üçüncü sorguda $[2, 2]$ , alt dizi $[1]$ 'dir. Mevcut tek alt parça $[1]$ 'dir (değeri $3$ ). En küçük eksik değer $2$ 'dir ( $[0]$ dizisi).

İkinci test durumunda dizi $a = [1, 1, 1, 1]$ a = [1, 1, 1, 1] şeklindedir. $[1, 4]$ sorgusu için $[0]$ dizisi (değeri $2$ ) hiç görülmez, bu yüzden cevap $2$ 'dir.

Üçüncü test durumunda dizi $a = [1, 0, 0, 1]$ a = [1, 0, 0, 1] şeklindedir.

$[1, 3]$ sorgusu için alt dizi $[1, 0, 0]$ [1, 0, 0]'dır. $[0], [1], [0, 0], [1, 0]$ [0], [1], [0, 0], [1, 0] alt parçalarını (değerleri $2, 3, 4, 6$ 2, 3, 4, 6) içerir. En küçük eksik değer $5$ 'tir ( $[0, 1]$ dizisi).
$[2, 4]$ sorgusu için alt dizi $[0, 0, 1]$ [0, 0, 1]'dir. $[0], [1], [0, 0], [0, 1]$ [0], [1], [0, 0], [0, 1] alt parçalarını (değerleri $2, 3, 4, 5$ 2, 3, 4, 5) içerir. En küçük eksik değer $6$ 'dır ( $[1, 0]$ dizisi).
$[1, 4]$ sorgusu için alt dizi $2, 3, 4, 5$ 2, 3, 4, 5 ve $6$ değerlerini içerir. En küçük eksik değer $7$ 'dir ( $[1, 1]$ dizisi).

Puanlama

Alt görev 1 (100 puan): $\sum n \leq 2000$ \sum n \le 2000 ve $\sum q \leq 2000$ \sum q \le 2000.
Alt görev 2 (150 puan): $\sum n \leq 40000$ \sum n \le 40000 ve $\sum q \leq 40000$ \sum q \le 40000.
Alt görev 3 (250 puan): Ek kısıtlama yoktur.