T1:

加帕里的聚会

256MB / 1s ; japari.cpp / c / pas / in / out

【题目描述】

加帕里公园里有n个区域，n-1条道路将它们连接到了一起，形成了一个树的结构。开始时，第i个区域有Ai个friends，但是由于砂之星的作用，有时从x区域到y区域的简单路径上的所有区域的friends数量都会增加v，有时从x区域到y区域的简单路径上所有区域的friends数量都会变成v。

有时，从x区域到y区域的简单路径上所有区域的friends想要聚会，聚会时需要从所有参加聚会的friends中选择一部分作为staff。加帕里的friends都很喜欢质数，因此她们希望staff和非staff的参与者的数量都是质数。

请你告诉她们，每次聚会是否存在一种方案满足她们的要求。

 

【输入格式】

第一行两个整数n,m，表示friends数量和事件数量。

接下来一行n个数，第i个数表示Ai。

接下来n-1行，每行2个数x,y，表示x和y之间有一条无向道路。

接下来m行，每行第一个整数opt表示事件类型。

若opt=1，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都增加v。

若opt=2，接下来三个整数x,y,v，表示从x区域到y区域的简单路径上的所有区域的friends数量都变为v。

若opt=3，接下来两个整数x,y，表示从x区域到y区域的简单路径上的所有区域的friends进行聚会。

 

【输出格式】

对于每个3事件，若可以让staff和非staff的数量都为质数，输出一行SUGOI，否则输出一行TANOSHI。

 

【样例数据】

japari1.in	japari1.out
3 4 1 2 1 2 1 3 2 2 2 1 4 1 3 3 -1 2 2 2 2 3 1 3	SUGOI
japari2.in	japari2.out
4 6 2 4 0 0 2 1 3 2 4 3 2 1 4 2 1 4 4 9 1 3 2 -2 2 4 2 5 3 1 4 3 4 4	TANOSHI SUGOI

 

【样例解释】

在第一个样例中，三个区域的friends数量依次为4、2、0，询问的friends和为6，可以分成两组，每组的friends数量都为3。

在第二个样例中，四个区域的friends数量依次为2、5、5、5，第一个询问的friends和为17，无法分成两组。第二个询问的friends和为5，可以分为两组，每组的friends数量分别为2、3。

 

【数据范围】

对于30%的数据，n,m≤5000。

对于另30%的数据，对于i＞1，第i个区域与第i-1个区域直接相连。

对于100%的数据，1≤n,m≤100000，1≤x,y≤n，一直满足0≤Ai,S≤10000000。在增加事件中v可能为负数。

 

解析：