Yu Ling(Ling YueZheng) and Colorful Tree
题号：NC223948
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Yu Ling (Ling YueZheng) gives you a weighted tree of n vertices, rooted at vertex 1, each weight is called the color of that vertex.

She will ask you to design an appropriate data structure, in order to maintain the tree, allowing her to perform q operations on it.

Those q operations have two types:
  • - 0 \ u \ x — this operation assigns x to the color of vertex u, which have not been dyed before by any color.
  • - 1 \ u \ l \ r \ x — this operation queries the distance of u to the nearest ancestor v of vertex u which satisfies all of the following three requirements:
- v has been dyed to some color before;
- v possesses a color y satisfying l \leq y \leq r;
- v possesses a color y satisfying y \equiv 0 \mod x.

After any query, you will need to output the distance of u to the ancestor v.

输入描述:

The first line contains two integers n, q \ (1 \leq n, q \leq 1.1 \times 10^5).

The next n - 1 lines contains three integers u_i, v_i, w_i \ (1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^9) each, describing an edge of the tree, connecting vertex pair (u_i, v_i) with a distance of w_i.

The next q lines describe operations, the i-th line describes the i-th operation in one of these two formats:
- 0 \ u \ x — representing an operation of the zeroth type.
- 1 \ u \ l \ r \ x — representing an operation of the first type.

Additionally, it is guaranteed that for any operation of the zeroth type, 1 \leq u \leq n, 1 \leq x \leq n, any color that has been used to dye any vertex before will never be used again to dye any vertex; and that for any operation of the first type, 1 \leq u \leq n, 1 \leq l \leq r \leq n, 1 \leq x \leq n.

输出描述:

Uncertain lines, each line contains one integer \Delta, namely the distance of u to the ancestor v; in the case which there doesn't exist any ancestor of u satisfying all of the requirements, just print "Impossible!" instead of any distances.
示例1

输入

复制 
8 10
1 2 556896192
4 3 64145383
4 8 137990197
7 6 928990652
6 1 928332054
5 1 1874224672
4 6 1500534450
0 1 6
1 7 2 6 1
0 2 2
0 4 5
1 8 1 6 2
1 3 5 6 5
0 5 8
1 2 6 8 3
0 6 3
1 3 1 5 2

输出

复制 
1857322706
2566856701
64145383
556896192
Impossible!
示例2

输入

复制 
41 47
23 3 1499286373
32 3 1882254169
5 32 710806646
27 8 1989679844
13 29 2092302828
35 41 463534124
6 17 1655401219
35 30 1400532883
13 1 1076857488
36 40 2079467050
24 12 912692557
41 14 154268950
18 8 506135061
7 22 2070713265
21 38 959595731
9 40 1432621336
17 26 519417766
30 40 1366039941
26 41 845259469
34 7 1949484675
27 28 1850136356
29 12 270071038
28 16 1131734903
33 9 486097838
4 10 206555493
39 17 1140777575
10 39 1542543386
21 25 1583282967
25 11 1425078687
18 23 1964360034
34 24 1056869686
16 38 728391261
32 19 479809208
15 12 694164755
37 24 927579989
25 2 1075604576
22 31 655038568
33 31 2123779560
11 37 1469040861
20 19 1020417997
0 14 32
1 39 11 17 8
0 9 10
1 11 4 36 9
1 17 2 28 2
1 3 1 20 4
0 7 37
1 6 12 19 14
0 13 6
0 24 8
0 40 25
0 8 21
0 27 13
0 1 23
0 19 16
0 36 31
1 40 1 37 4
0 30 2
0 3 18
0 12 34
0 25 36
1 5 20 23 4
0 10 11
1 19 13 34 2
0 32 20
0 33 29
1 32 25 39 1
1 3 36 37 5
0 22 4
0 37 22
0 39 5
0 20 17
1 5 2 21 2
1 10 7 12 7
0 4 3
1 3 11 38 15
1 32 1 16 2
0 11 19
0 23 28
0 35 9
0 38 38
0 18 33
1 32 36 40 9
1 11 3 14 3
1 32 4 11 2
1 5 26 37 22
1 10 8 14 5

输出

复制 
Impossible!
Impossible!
6027405519
Impossible!
Impossible!
9774604928
Impossible!
0
14094856699
Impossible!
710806646
Impossible!
Impossible!
17916556236
14094856699
5671687273
17916556236
Impossible!
8710726480

备注: