乐乐做了个梦，梦见自己当了国王。乐乐王国有N座城市（编号从1~N，首都的编号为1）。乐乐王国的道路构成树状结构：首都1与几个大城市相连，这几个大城市又通过道路与一些稍小的城市相连……严格地说，这N座城市构成一棵有根树（1为树根），城市i的管理区域为以i为根的子树。
道路都是双向的。经过每条道路需要收费，从城市A到城市B的花费为A到B的简单路径上所有道路的费用之和（不妨称之为城市对(A, B)之间的花费）。显然，一棵树上任意两点之间的简单路径（即不能重复经过某个点的路径）是唯一的。
由于物价飞涨，经过一番缜密的思考，乐乐决定重新规划自己国家的道路收费。具体来说，他要进行Q个操作，每个操作是如下两种类型：
INC u v w
——表示u到v的路径上，所有的道路的收费增加w；
ASK p
——表示询问城市p的管理区域中，所有的“城市对”的花费之和。比如，城市p的管理区域（即以p为根子树）中有城市c₁, c₂, c₃, …，c_s（这里面包括p），询问所有的城市对(c₁, c₂), (c₁, c₃), …, (c₂, c₃), …,(c_s-1, c_s)的花费之和。
乐乐把这个问题交给你，快帮帮他吧！

第一行输入两个正整数N，Q，分别表示城市的数目和操作的数目。
接下来有N – 1行，第i行是两个正整数pi, ci，表示城市pi是城市i的父亲结点，且连接pi和i的道路的初始收费为ci（1≤ci≤1000）。
接下来有Q行，每行是如下两种类型之一：
INC u v w (u, v, w都是整数，且1≤u, v≤N, 0≤w≤1000，注意u, v可能相等)
ASK p   (p是正整数，且p≤N)
意义如题目所述。

对每个ASK类型的操作，输出所求的答案。请你输出答案对2019取模后的结果。

5 5
1 1
2 5
1 2
2 1
INC 2 4 2
INC 3 4 1
ASK 2
INC 2 5 3
ASK 1

14
84

乐乐王国的地图如下：
如图1，城市1的管理区域是1,2,3,4,5；城市2的管理区域是2,3,5；城市3,4,5的管理区域是它们自己。
经过前两次操作，道路费用变化如图2。
这时，(2,3),(2,5),(3,5)的费用和=6+1+7=14。
再进行一次修改（第4个操作），变化如图3。
这时，(1,2)(1,3)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(3,5)(4,5)的总费用为：
4+10+5+8+6+9+4+15+10+13=84

1≤Q,N≤50000，树的深度不超过10000，其他输入数据的范围在输入格式中已给出。