"Waaah! How can there be such a strange array!"

Kruskal-chan stared at the blackboard covered in $+1$s and $-1$s, feeling completely overwhelmed.

"Senior, senior!" her junior tugged at her sleeve. "If you are given an interval, and the numbers inside can be rearranged arbitrarily, how many permutations are there such that the sum of the products of all non-empty contiguous subarrays is exactly $k$?"

Facing those sparkling eyes, Kruskal-chan had no choice but to bite the bullet and accept the challenge.

Sigh, today's club activity doesn't seem very peaceful either...

Given an array $a$ of length $n$, where each element is either $1$ or $-1$.

Given a constant $k$ and $q$ queries. Each query specifies $l$ and $r$. Calculate: if you can arbitrarily rearrange the elements in the index range $[l, r]$, how many permutations are there such that the sum of the products of all non-empty contiguous subarrays of the new array (which still has length $n$) is equal to $k$? The result should be taken modulo $998244353$.

Note: Even if two different permutations result in the same array, they are considered distinct permutations.

Input

The input contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), the number of test cases.

Each test case begins with a line containing three integers: the array length $n$ ($1 \le n \le 10^5$), the constant $k$ ($|k| \le \frac{n(n+1)}{2}$), and the total number of queries $q$ ($1 \le q \le 10^5$).

The next line contains $n$ integers, where the $i$-th integer represents $a_i$, satisfying $|a_i| = 1$.

The next $q$ lines each contain two integers, where the $i$-th line contains $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

It is guaranteed that $\sum n, \sum q \le 10^5$.

Output

Output $q$ lines, each containing one integer representing the result of the query.

Examples

Input 1

2
5 -3 3
1 -1 -1 1 -1
1 4
2 5
3 3
3 6 1
1 -1 -1
1 3

Output 1

8
12
0
0

Note

For the first query of the first test case, the first four elements must be arranged as $(1, -1, 1, -1)$ or $(-1, 1, -1, 1)$, resulting in a total of $8$ permutations that satisfy the requirement.