Виключення бітового підвідрізка

Вхідні дані

Перший рядок містить одне ціле число $t$ (1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілих числа $n$ та $q$ (1 \le n, q \le 2 \cdot 10^5) — довжину бінарного масиву та кількість запитів.

Другий рядок кожного тестового випадку містить $n$ цілих чисел a_1, a_2, \dots, a_n (a_i \in \{0, 1\}), розділених пробілами, — елементи масиву.

Наступні $q$ рядків описують запити. Кожен рядок містить два цілих числа $l$ та $r$ (1 \le l \le r \le n) — межі відрізка запиту.

Гарантується, що як сума $n$, так і сума $q$ за всіма тестовими випадками не перевищують 2 \cdot 10^5.

Вихідні дані

Для кожного запиту виведіть в окремому рядку одне ціле число — мінімальне числове значення бінарної послідовності, яка не зустрічається як неперервний підвідрізок у a[l \dots r], за модулем $998244353$.

Приклади

Примітка

У першому тестовому випадку масив дорівнює a = [0, 1, 0].

• У першому запиті $[1,3]$ наявні такі неперервні підвідрізки: [0], [1], [0, 1], [1, 0] та [0, 1, 0]. Їхні десяткові значення дорівнюють відповідно 2, 3, 5, 6 та $10$. Найменше значення, яке не утворюється, — це $4$, що відповідає послідовності $[0,0]$.

• У другому запиті $[1,2]$ підмасив дорівнює $[0,1]$. Наявні підвідрізки: $[0],[1]$ та $[0,1]$. Найменше відсутнє значення знову дорівнює $4$ (послідовність $[0,0]$).

• У третьому запиті $[2,2]$ підмасив дорівнює $[1]$. Єдиний наявний підвідрізок — $[1]$ (значення $3$). Найменше відсутнє значення — $2$ (послідовність $[0]$).

У другому тестовому випадку масив дорівнює a = [1, 1, 1, 1]. Для запиту $[1,4]$ послідовність $[0]$ (значення $2$) не зустрічається ніколи, тому відповідь дорівнює $2$.

У третьому тестовому випадку масив дорівнює a = [1, 0, 0, 1].

• Для запиту $[1,3]$ підмасив дорівнює [1, 0, 0]. Він містить [0], [1], [0, 0], [1, 0] (значення 2, 3, 4, 6). Найменше відсутнє значення — $5$ (послідовність $[0,1]$).

• Для запиту $[2,4]$ підмасив дорівнює [0, 0, 1]. Він містить [0], [1], [0, 0], [0, 1] (значення 2, 3, 4, 5). Найменше відсутнє значення — $6$ (послідовність $[1,0]$).

• Для запиту $[1,4]$ підмасив містить значення 2, 3, 4, 5 та $6$. Найменше відсутнє значення — $7$ (послідовність $[1,1]$).

Оцінювання

• Підзадача 1 (100 балів): \sum n \le 2000 та \sum q \le 2000.

• Підзадача 2 (150 балів): \sum n \le 40000 та \sum q \le 40000.

• Підзадача 3 (250 балів): Без додаткових обмежень.