因为一些众所周知的原因，lyt并没有得到他的板栗栗，所以他在情人节这天买了一堆花送给自已。

    然而他的队友you_xiao和对象出去玩了，lyt感到很无聊，他将那些花摆成了一排，每个格子里都有一些花。

    更准确的说，有一个1*n的图，第一个格子里有1朵花，第二个格子里有1朵花，第i个格子有$f(i)=f(i-1)+f(i-2)$朵花$(i>2)$

    you_xiao回来后，发现有这些鲜花，他很好奇一个区域里有多少花。

    更准确的说：给你两个数$(l,r)$，请问在这个区间内，奇数（或偶数）格子的花的和（mod 998244353）是多少？

    摆了这么多花后，lyt也不知道到底有多少花了，他想问问聪明的你

第一行一个整数n(1<=n<=1e6)，代表有多少个格子;
第二行一个整数q(q<=1e6)代表有q组询问;
接下来q行，每行三个整数l,r,x;(0<x<=2,l<=r&&r<=n)
如果x=1表示询问区间[l,r]之间奇数格子的鲜花有多少个(若无奇数格子则为0);
如果x=2表示询问区间[l,r]之间偶数格子的鲜花有多少个(若无偶数格子则为0);

输出q行,每行一个整数表示答案.