该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

Today, Rikka is going to learn how to use BIT to solve some simple data structure tasks. While studying, She finds there is a magic expression \(x\)&\(-x\) in the template of BIT. After searching for some literature, Rikka realizes it is the implementation of the function \(lowbit(x)\).

\(lowbit(x)\) is defined on all positive integers. Let \(a_1...a_m\) be the binary representation of x while a1 is the least significant digit, k be the smallest index which satisfies \(a_k\) = 1. The value of \(lowbit(x)\) is equal to \(2^k-1\).

After getting some interesting properties of \(lowbit(x)\), Rikka sets a simple data structure task for you:

At first, Rikka defines an operator f(x), it takes a non-negative integer x. If x is equal to 0, it will return 0. Otherwise it will return \(x-lowbit(x)\) or \(x+lowbit(x)\), each with the probability of 0.5.

Then, Rikka shows a positive integer array A of length n, and she makes m operations on it.

There are two types of operations:
1. 1 L R, for each index i ∈ [L,R], change \(A_i\) to \(f(A_i)\).
2. 2 L R, query for the expectation value of \(A_L+...+A_R\). (You may assume that each time Rikka calls f, the random variable used by f is independent with others.)

Format

Input

The first line contains a single integer t(1 ≤ t ≤ 3), the number of the testcases.

The first line of each testcase contains two integers n,m(1 ≤ n,m ≤ \(10^5\)). The second line contains n integers \(A_i\)(1 ≤ \(A_i\) ≤ \(10^8\)).

And then m lines follow, each line contains three integers t,L,R(t ∈ {1,2}, 1 ≤ L ≤ R ≤ n).

Output

For each query, let w be the expectation value of the interval sum, you need to output w * \((2^n)^m\) MOD 998244353.
It is easy to find that w * \((2^n)^m\) must be an integer.

Sample 1

Input

1
3 6
1 2 3
1 3 3
2 1 3
1 3 3
2 1 3
1 1 3
2 1 3

Output

1572864
1572864
1572864

Limitation

1s, 128MB for each test case.

Hint

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original