트럭

머나먼 세계에 N개의 마을이 있고, 이 마을들에는 영웅들이 살며 다가올 전투를 준비하고 있다. 그러나 물자를 준비하던 중 금이 더 필요해졌다! 식량과 무기를 더 사려면 돈이 필요했기 때문이다. 그래서 영웅들은 마을 사이로 금을 운반하기 위해 가장 안전하고 믿을 만한 운송 수단인 트럭을 이용한다.

N개의 마을은 N - 1개의 도로로 연결되어 있어, 두 마을 사이를 하나 이상의 도로로 이동하는 경로가 정확히 하나 존재한다. 도로에는 1번부터 N - 1번까지 번호가 붙어 있고 각각 길이 Di를 가진다. 또한 각 도로에는 통행료로 일정량의 금괴를 받는 문지기가 있으며, 도로마다 통행료가 다를 수 있고 차량은 도로를 이용하기 전에 통행료를 내야 한다. 특히 i번째 도로는 마을 Ai와 Bi를 연결하고, 길이가 Di이며 통행료가 Ti이다.

영웅들은 당연히 트럭을 운행할 때 드는 연료비도 부담해야 한다. 트럭이 사용하는 연료의 양은 현재 운반 중인 금의 양에 따라 달라진다. 특히 트럭이 X개의 금괴를 운반하며 1만큼의 거리를 이동하면 X만큼의 연료를 소모한다.

영웅들은 여러 번의 운송을 계획했고, i번째 운송은 G개의 금괴를 마을 Ai에서 Bi로 운반하는 것이다. (G는 모든 운송에서 동일하다.) 즉, 통행료를 내는 데 쓰는 금괴 외에도 추가로 G개를 운송이 끝난 뒤 목적지 마을에 전달해야 한다. 영웅들은 연료 사용량을 최소화하려 하며, 최적의 경로를 택하고 통행료를 내기 위해 운반할 금괴의 수를 최적으로 정해 연료 사용량을 최소화한다. 그러나 운송 사이에 일부 도로의 통행료가 바뀔 수 있고, 이는 이후 운송의 연료 사용량에 영향을 준다.

영웅들은 전투 준비로 바빠 연료 사용량을 계산할 시간이 없으므로, 각 운송마다 대신 계산해 주려 한다(이것이 질의 연산이다). 운송 사이에 일부 도로의 통행료가 바뀔 수 있다는 점을 기억하자(이것이 갱신 연산이다). 계획한 운송과 도로 통행료 변경이 일어나는 올바른 순서가 주어질 때, 각 운송의 연료 소비량을 계산하라. 결과가 매우 클 수 있으므로 답을 109 + 7로 나눈 나머지를 출력해야 한다.

프로그램은 표준 입력에서 읽어야 한다.

첫째 줄에는 두 정수 N과 G가 주어진다. N은 마을의 수, G는 각 운송에서 운반할 금괴의 수이다.

이어서 N - 1개의 줄이 주어진다. i번째 줄에는 4개의 정수 Ai, Bi, Di, Ti가 주어진다.

다음 줄에는 하나의 정수 Q가 주어진다. Q는 계획된 운송과 도로 통행료 변경의 총 횟수, 즉 질의와 갱신 연산의 총 개수이다.

이어서 Q개의 줄이 주어진다. i번째 줄은 정수 Vi로 시작한다.

• Vi = 0이면 갱신 연산이다. 이 줄에는 정수 X Y T가 더 주어지며, 마을 X와 Y를 연결하는 도로의 통행료가 T로 바뀐다는 뜻이다.
• Vi = 1이면 질의 연산이다. 이 줄에는 정수 X Y가 더 주어지며, 마을 X에서 Y로 가는 운송을 뜻한다.

프로그램은 표준 출력에 출력해야 한다.

각 질의 연산마다 한 줄에 하나의 정수를 출력한다. 이는 그 운송에서 사용한 최소 연료량을 109 + 7로 나눈 나머지이다.

각 운송의 결과는 입력에 주어진 순서와 같은 순서로 출력해야 한다.

• 2 ≤ N ≤ 100 000
• 1 ≤ Q ≤ 100 000
• 1 ≤ Ai, Bi ≤ N
• 1 ≤ Di, Ti, G ≤ 109