Light

Problem

You bought a tree-shaped lighting fixture called a tree light.

This luminaire has n contacts, each numbered from 0 to n-1. Each contact consists of a light bulb that can express 10 levels of brightness and a device for switching the state of the light bulb. Initially, the brightness of the bulbs at all contacts is zero.

In addition, there is a cable wire between the contacts. All contacts are connected by n-1 cable lines and are hung with contact 0 facing up. Here, a set of contacts connected to the contact i via zero or more cable wires downward from the contact i is called a subtree rooted at the contact i.

You take one of the following actions with respect to this luminaire:

• count (r, x, y): Counts the number of light bulbs with a brightness of x or more and y or less among the light bulbs of the contact contained in the subtree rooted at the contact r.
• change (r, x, y): Change the brightness of all the bulbs of the contacts contained in the subtree rooted at the contact r to y, whose brightness is exactly x.

Since q actions are given, output the number of light bulbs at that time each time count (r, x, y) is given.

Constraints

• 1 ≤ n ≤ 105
• 1 ≤ q ≤ 105
• 0 ≤ ui, vi, ri ≤ n−1 (ui ≠ vi)
• 0 ≤ xi, yi ≤ 9 (when ti = 1 xi ≤ yi)

Input

The input is given in the following format.

n q u1 v1 u2 v2 ... un−1 vn−1 t1 r1 x1 y1 t2 r2 x2 y2 ... tq rq xq yq

The number of contacts n that make up the tree light and the number of actions you take q are given on the first line, separated by blanks. Cable line information is given on the following n-1 line, separated by blanks. The information of the i-th cable line indicates that the cable line i connects the contact ui and the contact vi with the contact ui facing up. n & plus; The actions you take are given in the q lines after the first line, separated by blanks. If ti = 1, it represents count (ri, xi, yi), and if ti = 2, it represents change (ri, xi, yi).

Output

For each count (ri, xi, yi), output the answer on one line.

Examples

Input

7 5 0 1 1 2 1 3 0 4 4 5 4 6 1 0 0 9 2 0 0 5 2 1 5 8 1 0 5 8 1 0 8 8

Output

7 7 3

Input

7 5 0 1 1 2 2 3 0 4 4 5 5 6 2 1 0 5 2 4 0 6 2 3 5 6 2 5 6 5 1 0 0 5

Output

5

inputFormat

outputFormat

output the number of light bulbs at that time each time count (r, x, y) is given.

Constraints

• 1 ≤ n ≤ 105
• 1 ≤ q ≤ 105
• 0 ≤ ui, vi, ri ≤ n−1 (ui ≠ vi)
• 0 ≤ xi, yi ≤ 9 (when ti = 1 xi ≤ yi)

Input

The input is given in the following format.

n q u1 v1 u2 v2 ... un−1 vn−1 t1 r1 x1 y1 t2 r2 x2 y2 ... tq rq xq yq

The number of contacts n that make up the tree light and the number of actions you take q are given on the first line, separated by blanks. Cable line information is given on the following n-1 line, separated by blanks. The information of the i-th cable line indicates that the cable line i connects the contact ui and the contact vi with the contact ui facing up. n & plus; The actions you take are given in the q lines after the first line, separated by blanks. If ti = 1, it represents count (ri, xi, yi), and if ti = 2, it represents change (ri, xi, yi).

Output

For each count (ri, xi, yi), output the answer on one line.

Examples

Input

7 5 0 1 1 2 1 3 0 4 4 5 4 6 1 0 0 9 2 0 0 5 2 1 5 8 1 0 5 8 1 0 8 8

Output

7 7 3

Input

7 5 0 1 1 2 2 3 0 4 4 5 5 6 2 1 0 5 2 4 0 6 2 3 5 6 2 5 6 5 1 0 0 5

Output

5

样例

7 5
0 1
1 2
1 3
0 4
4 5
4 6
1 0 0 9
2 0 0 5
2 1 5 8
1 0 5 8
1 0 8 8

7
7
3

</p>