异或询问

题号：NC201936
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个序列 $a_{1...n}$ ，定义 ${f(x)}$ 为有几个 $a_i$ 小于等于 ${x}$
现在有 ${Q}$ 次询问，每次给定 ${l,r,x}$ ，你需要求 $\displaystyle \sum_{i=l}^{r}f(i~xor~x)^2$ ，由于答案可能很大，你只需要输出答案对 ${998244353}$ 取模后的值即可。

输入描述:

第一行两个正整数 
第二行  个整数 
接下来  行，每行三个整数 ，表示一次询问
，，，

输出描述:

对于每次询问，输出一行一个整数表示答案

示例1

输入

复制

输出

复制

16
25
30