Problem: 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

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <array>

using namespace std;
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

using C = array<int, 10>;
constexpr C e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

struct Node {
    using NP = Node*;
    NP l, r;
    int sz;
    Node(int sz) : sz(sz) {
        fill(begin(cnt), end(cnt), 0);
        cnt[0] = 1;
        lz = e;
        if (sz == 1) return;
        l = new Node(sz/2);
        r = new Node(sz-sz/2);
        update();
    }
    C cnt;
    C lz;
    void push() {
        if (lz != e) {
            l->lzdata(lz);
            r->lzdata(lz);
            lz = e;
        }
    }
    void lzdata(C nx) {
        C ncnt = {};
        C nlz = {};
        for (int i = 0; i < 10; i++) {
            nlz[i] = nx[lz[i]];
        }
        for (int i = 0; i < 10; i++) {
            ncnt[nx[i]] += cnt[i];
        }
        lz = nlz;
        cnt = ncnt;
    }
    void update() {
        for (int i = 0; i < 10; i++) {
            cnt[i] = l->cnt[i] + r->cnt[i];
        }
    }
    int get(int a, int b, int c, int d) {
        if (b <= 0 || sz <= a) return 0;
        if (a <= 0 && sz <= b) {
            int u = 0;
            for (int i = c; i <= d; i++) {
                u += cnt[i];
            }
            return u;
        }
        push();
        return l->get(a, b, c, d) + r->get(a - sz/2, b - sz/2, c, d);
    }
    void cng(int a, int b, int c, int d) {
        // c -> d
        if (b <= 0 || sz <= a) return;
        if (a <= 0 && sz <= b) {
            C x = e;
            x[c] = d;
            lzdata(x);
            return;
        }
        push();
        l->cng(a, b, c, d);
        r->cng(a-sz/2, b-sz/2, c, d);
        update();
    }
};

int n, q;
VV<int> g;
V<int> lid, rid;
int nc = 0;
void precalc(int p, int b) {
    lid[p] = nc; nc++;
    for (int d: g[p]) {
        if (d == b) continue;
        precalc(d, p);
    }
    rid[p] = nc;
}

V<int> res;



int main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    g = VV<int>(n);
    lid = V<int>(n); rid = V<int>(n);
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    precalc(0, -1);

/*    for (int i = 0; i < n; i++) {
        cout << lid[i] << ":" << rid[i] << endl;
    }*/

    Node* tr = new Node(n);
    res = V<int>(q);
    for (int i = 0; i < q; i++) {
        int t, p, x, y;
        cin >> t >> p >> x >> y;
        int l = lid[p], r = rid[p];
        if (t == 1) {
            //count
            cout << tr->get(l, r, x, y) << endl;
        } else {
            //change
            tr->cng(l, r, x, y);
        }
    }
    return 0;
}