乘法和幂
题号：NC207503
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给了你一个数组，并规定了3种操作，操作1是把一个连续的区间内所有的数字变为，操作2是把一个连续的区间内所有的数字变为，操作3是询问你一个区间中所有数的积的对取模后的结果。

输入描述:

第一行一个正整数，表示一共有组输入。
对于每组输入，第一行输入一个正整数,表示数组的长度。第二行输入个数，表示数组里的元素。第三行输入一个正整数,表示操作的次数。
接下来行，每行先输入一个正整数，对应三种操作，对于操作1，输入三个数,代表把所有替换成,对于操作2，输入三个数,代表把所有替换成,对于操作3，输入两个数,询问区间里所有数的乘积对取模。

输出描述:

对于每个操作3输出一行。
示例1

输入

复制 
2
5
1 2 3 4 5
5
3 1 1
3 1 2
3 1 3
3 1 4
3 1 5
5
2 2 2 2 2
6
1 1 5 2
3 1 3
2 2 4 2
3 3 5
1 1 3 3
3 1 5

输出

复制 
1
2
6
24
120
64
256
6869905

说明

第一组
1
1*2
1*2*3
1*2*3*4
1*2*3*4*5
第2组
第1个操作以后，数组成了4，4，4，4，4
第2个操作 4*4*4
第3个操作以后，数组成了4，8，8，8，4
第4个操作8*8*4
第5个操作以后，数组成了64，512，512，8，4
第6个操作 64*512*512*8*4 这个数模10000019的结果就是6869905

备注:


\\ m = 3n