Kaka has recently become obsessed with Goose Goose Duck, and he is no longer satisfied with 15-player games. Therefore, he commissioned the kind-hearted Big-Headed Stickman to design a 3000-player version of Goose Goose Duck. However, because the Big-Headed Stickman needs to devote more time and energy to developing Lele's Apricot Blossom (current progress: game development tutorials found, like-minded individuals are welcome to join), he wrote a simplified version of "Kaka Kill" for Kaka.

The map of Kaka Kill is a tree with no more than 3000 nodes. Players are divided into four factions: Kaka, Goose, Duck, and Neutral. Note that there is only one Kaka in each game, along with some (possibly zero) Geese, some (possibly zero) Ducks, and some (possibly zero) Neutrals. In each game, every player has a starting point and an ending point, and they will move along the shortest path on the tree from the start to the end, moving one edge per turn.

Every player has a "kill" skill. The moment the skill is activated, the player can simultaneously attack all targets they wish to eliminate who are at the same location. The $i$-th player uses their kill skill every $t_i$ turns (meaning they will immediately use the skill as soon as the cooldown is reached), i.e., the $i$-th player attacks on turns $t_i, 2 \times t_i, \dots, k \times t_i, \dots$.

The rules for players eliminating others are as follows: – Kaka: Kaka wants to indiscriminately eliminate all players except himself. – Goose: Geese only want to eliminate the terrifying Kaka and will not cause damage to other players. – Duck: Ducks only want to eliminate Geese and will not cause damage to other players. – Neutral: Neutrals want to indiscriminately eliminate all players except themselves and Kaka, and will not cause damage to Kaka.

Specifically, if two players activate their elimination skills against each other at the same time, if one party is Kaka, Kaka will be eliminated while the other party will survive if they are not being attacked by anyone else (Kaka's duels always fail); otherwise, both parties will be eliminated simultaneously.

Players who successfully reach their destination immediately win and leave the game (they can no longer be eliminated by other players, nor can they eliminate other players).

Specifically, in the same turn, the following four events occur in order: 1) All players still on the field move; 2) Players who reach their destination win and leave the game; 3) All players who can use their skill, except Kaka, attack their intended targets. Note that an attacking player will simultaneously attack all targets they wish to eliminate who are at the same location (yes, because it is a forty-meter-long blade, one swing can strike all targets at once). 4) If Kaka is not dead, Kaka attacks (Kaka's hand speed is too slow).

Given the map and player roles, each player's starting and ending points, and each player's skill cooldown $t_i$, output the list of winning players in ascending order of their player ID.

Input

The first line contains two integers $n$ and $m$, representing the number of nodes and the number of players.

The next $n-1$ lines each contain two integers $x$ and $y$, representing an edge between $x$ and $y$.

The next $m$ lines each contain four integers $op$, $tim$, $s$, and $t$, representing the player's role, skill cooldown, starting point, and ending point.

• If $op = 1$, the player is Kaka; the data guarantees there is exactly one Kaka.
• If $op = 2$, the player is a Goose.
• If $op = 3$, the player is a Duck.
• If $op = 4$, the player is a Neutral.

Output

The first line outputs an integer $sum$, representing the number of players who survived until the end.

The next $sum$ lines output the IDs of the surviving players, in ascending order of their player ID.

Examples

Input 1

2 1
2 1
1 30 1 2

Output 1

1
1

Input 2

5 4
2 1
4 2
2 5
1 3
4 3 3 5
1 1 1 4
2 2 5 4
3 1 2 3

Output 2

3
1
2
4

Input 3

5 5
1 2
1 3
2 4
2 5
1 2 1 5
2 3 1 4
3 1 4 2
2 1 1 2
4 2 3 4

Output 3

5
1
2
3
4
5

Note

$1 \le n, m, tim \le 3000$, $op \in \{1, 2, 3, 4\}$, $1 \le s, t \le n$.

Figure 1. Illustration of the elimination process in the game.