국제 메시 기구

문제

야구선수인 메시는 국제 메시 기구(IMO, International messi organization)의 금고 관리자이다. 트리를 사랑하는 메시는 금고를 금고 1이 루트인 트리 모양으로 연결해서 관리한다고 한다.

업무시간에 A+B를 풀고 있던 메시는 메일 하나를 받았는데, 그 메일에는 '메시 흑역사.jpg.exe'라는 이름의 첨부파일이 하나 있었다. 안 그래도 어제 도난 사건으로 금고 N개가 다 털려 0원밖에 남지 않아 해고당할 위기에 처했는데 흑역사까지 드러날 위기에 처한 메시는 한 치의 고민도 없이 첨부파일을 열었다. 그러자 이상한 콘솔 창이 등장했다!

금★고의 요☆정 지♨니! 금고 속의 돈을 늘려드립니다! 명령어를 입력하세요. 명령어의 목록은 다음과 같습니다.

• "1 X V" 금고 X의 서브트리에 있는 모든 금고에 V원을 더합니다. (1 ≤ X ≤ N, 1 ≤ V ≤ $10^{9}$)

• "2 X Y V" 금고 X부터 금고 Y까지의 경로에 있는 모든 금고에 V원을 더합니다. 단, 경로는 경계를 포함합니다. (1 ≤ X, Y ≤ N, 1 ≤ V ≤ $10^{9}$)

• "3 X V" 금고 X의 서브트리에 있는 모든 금고의 돈을 V배 합니다. (1 ≤ X ≤ N, 0 ≤ V ≤ $10^{9}$)

• "4 X Y V" 금고 X부터 금고 Y까지의 경로에 있는 모든 금고의 돈을 V배 합니다. 단, 경로는 경계를 포함합니다. (1 ≤ X, Y ≤ N, 0 ≤ V ≤ $10^{9}$)

• "5 X" 금고 X의 서브트리에 있는 모든 금고의 돈을 합한 값을 출력합니다. (1 ≤ X ≤ N)

• "6 X Y" 금고 X부터 금고 Y까지의 경로에 있는 모든 금고의 돈을 합한 값을 출력합니다. 단, 경로는 경계를 포함합니다. (1 ≤ X, Y ≤ N)

메시는 도난 사건을 없던 일로 만들 기회라고 생각하여 명령어를 입력했지만, 이 파일은 당연하게도 바이러스라서 메시가 3개월간 짜던 A+B의 코드를 다 날려버렸다. 화가 난 메시는 위의 명령어를 실행하는 프로그램을 직접 만들기로 했다.

입력

첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000)

다음 N-1줄 중 i번째 줄에는 $S_{i}$, $E_{i}$가 주어지며, 이는 금고 $S_{i}$와 금고 $E_{i}$가 연결되어 있다는 뜻이다. (1 ≤ $S_{i}$, $E_{i}$ ≤ N)

금고가 연결된 모양은 올바른 트리 모양이다.

다음 Q줄에는 명령어들이 한 줄에 하나씩 주어진다.

출력

출력 명령어가 주어질 때마다 값을 출력한다. 단, 메시의 컴퓨터는 최신 트렌드인 4294967296비트 컴퓨터와는 다르게 32비트 컴퓨터이므로 $2^{32}$로 나눈 나머지를 대신 출력한다.

5 10
2 4
4 3
5 4
2 1
3 1 82
6 3 5
2 2 5 45
2 3 2 70
6 3 5
5 3
4 2 1 47
1 1 95
6 3 2
4 5 1 38

0
230
70
5875

10 20
3 7
5 6
10 9
6 8
10 2
6 3
1 3
6 4
10 4
1 10 97
1 10 50
3 9 9
5 5
1 8 27
5 10
2 8 7 20
2 4 4 41
2 2 5 92
3 4 96
3 5 12
1 7 32
2 7 3 75
4 5 6 60
6 8 7
6 1 2
3 9 0
1 3 20
6 1 1
1 6 82

0
1617
6989
65471
0

출처

• 문제를 만든 사람: imeimi2000