文理学院程序设计在线练习


GCD大师

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 27   Accepted Submission(s): 13
Problem Description

小太阳有n个数字在一行上。首先,它们全都等于1。除此之外,小太阳对素数感兴趣。他会选择一个连续的区间[l,r]和一个素数x,然后对于[l,r]上的每一个数字a[i],把它变成a[i]*x。为了简化这个问题,x等于2或者是3。在m次操作后,小太阳想知道所有数字的最大公约数。

Input

第一行包含一个整数t(1<=t<=10)表示有t个例子。
对于每个例子,第一行包含两个整数n(1<=n<=100000)和m(1<=m<=100000)。n代表有n个数字,m代表有m次操作。
接下来有m行,每行包含三个数字,l[i](1<=l[i]<=n),r[i](l[i]<=r[i]<=n),x[i](x[i]∈{2, 3})。

Output

对于每个例子,输出一个整数代表所有数字的最大公约数。答案可能非常巨大,需要对998244353取模。

Sample Input
2 
5 3 
1 3 2 
3 5 2 
1 5 3 
6 3  
1 2 2  
5 6 2 
1 6 2
Sample Output
6
2
Hint

对于第一个例子,在所有操作结束后,数字变成[6, 6, 12, 6, 6]。所以最大公约数是6。
比赛时:Time Limit 1s。

Source

2019元培院赛