問題文

初めに,$2$つの自然数$N,K$が与えられています.

カホさんは自然数のペア$(L,R)$に対し以下を満たす整数のみから構成される長さ$N$の数列$A$の個数に興味があります.

・$0 \le A_i < 2^K\ (1 \le i \le N)$

・$L \le A_1 \oplus A_2 \oplus ... ... \oplus A_N \le R$

彼女は上記のタイプのクエリに$Q$回答えようとしましたが,XORを習ったばかりの彼女には難しいようで

代わりにXORのエキスパートであるあなたに助けを求めてきました.

彼女の代わりに上記のクエリに$Q$回答えてください.なお結果は$mod\ 998244353$で出力してください.

(注記 : $\oplus$は排他的論理和(Exclusive OR = XOR)を指す)

制約

・入力はいずれも整数である

・$1\le N \le 10^6$

・$1\le K \le 60$

・$1\le Q \le 10^5$

▷各クエリにおいて以下が成り立つ.

・$0\le L \le R < 2^{K}$

入力

入力は以下の形式で与えられます.

N K Q
Query_1
Query_2
.
.
.
Query_Q

出力

すべてで$Q$行出力してください.

$i$行目には$i$番目のクエリに対する数列$A$の個数を$mod\ 998244353$で出力してください.

最後に改行してください.

サンプル

2 3 4
2 3
0 6
3 3
6 7

16
56
8
16

5 5 1
17 30

14680064

1000000 60 2
695360817523154042 708792922384807709
334945677305323519 510742335751990503

568318416
47700334

結果は$mod\ 998244353$で出力してください.