Кратко напомним правила игры «Ним». Имеется $$$n$$$ кучек камней, при этом в кучке $$$i$$$ изначально лежит какое-то число камней. Два игрока по очереди выбирают непустую кучку и берут из нее произвольное положительное (строго больше $$$0$$$) количество камней. Проигрывает тот, кто не может сделать ход.

Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Артем и Руслан решили играть в Ним на подотрезках массива. Каждый из $$$q$$$ раундов определяется отрезком $$$(l_i, r_i)$$$, где элементы массива $$$a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$$$ рассматриваются как размеры кучек камней.

До начала игры Руслан может удалить любое количество кучек из выбранного подотрезка. Однако хотя бы одна кучка должна остаться, поэтому в рамках одного раунда он может удалить не более $$$(r_i - l_i)$$$ кучек. Разрешается удалить $$$0$$$ кучек. После удаления ребята играют в Ним на всех оставшихся кучках из этого отрезка.

Все раунды независимы: удаления, произведенные в одном раунде, не влияют на исходный массив или другие раунды.

Руслану нужно удалить как можно больше кучек так, чтобы Артем, который будет ходить первым, проиграл.

Для каждого раунда определите:

1. максимальное количество кучек, которые Руслан может удалить;
2. количество способов выбрать максимальное количество кучек для удаления.

Два способа считаются различными, если существует такая позиция $$$i$$$, что в одном из способов кучка на позиции $$$i$$$ удаляется, а во втором — нет. Поскольку количество способов может быть большим, выведите его по модулю $$$998\,244\,353$$$.

Если в каком-то раунде Руслан не может сделать так, чтобы Артем проиграл, выведите для этого раунда одно число -1.