Background

The moon hides, tides rise, stars dim the silence of myriad isles, where no day or night ever changes. ————Excerpt from "The Chronicles of Shizhou City: Origins"

Shizhou City is surrounded by the sea and was founded 7325 years ago.

There is no day or night in Shizhou City; a single moon has hung in the sky since its inception, hence the name Shizhou (失昼), which means "lost day."

Yuelingshuang, the city lord of Shizhou, controls the Starkeeping Tower, which serves as a lighthouse for illumination in the city that never sees daylight. It is a spiritual pillar for the citizens. Yuelingshuang prefers to guard the Starkeeping Tower over being a city lord, as her other identity is the Starkeeper of Shizhou City.

The special environment of Shizhou City leads to unstable spatial conditions. According to the city's history, out of its seven thousand years, peaceful times total no more than three hundred years. Most of the time, parts of the city are under the influence of spatial storms. The Starkeeping Tower, relying on special spatial existence, also serves to transmit information. Under the influence of unstable space, this is the only way to maintain stable signals.

Problem Description

Shizhou City consists of \( N \) islands connected by \( N-1 \) spatial channels for information transmission.

As the Starkeeper of Shizhou City, Yuelingshuang has the ability to deploy Starkeeping Towers. Specifically, to transmit messages to each inhabited island through special spatial fluctuations, Yuelingshuang can deploy any number of Starkeeping Towers, but all deployed towers must form a chain connected by spatial channels at any given time.

Shizhou City is frequently troubled by spatial storms, which sometimes force all residents off an island. When this happens, the Starkeeping Tower no longer needs to transmit messages to that island. Only when the spatial storm subsides and residents return does the Starkeeping Tower need to resume message transmission to that island.

Due to spatial interference, Starkeeping Towers must rely on connected islands' spatial channels to transmit messages. Specifically, the energy consumed by a Starkeeping Tower to send a message to an island is the sum of the energy costs of all spatial channels between the tower's island and the target island. Of course, if a Starkeeping Tower sends a message to its own island, no energy is consumed. The signal transmissions of Starkeeping Towers to islands are independent, meaning that the energy transmissions of each Starkeeping Tower to each island do not interfere with each other.

As both the city lord and Starkeeper, Yuelingshuang is researching how to deploy Starkeeping Towers to minimize the energy consumed by message transmission. She has found records of spatial storm outbreaks and Starkeeping Tower deployments over the past seven thousand years in Shizhou City. However, due to the long history, the energy consumption details are unknown. Yuelingshuang now hopes you can help her reconstruct these historical records, as detailed in the input format.

Input Format

The first line contains three numbers \( N, Q, Type \), representing the number of islands in Shizhou City, the number of Yuelingshuang's queries, and special properties of the data point. \( Type \) is in binary; if the \( i-1 \)-th bit is 1, it indicates the presence of special property \( i \).

The next \( N-1 \) lines each contain three numbers \( u_i, v_i, w_i \), indicating a bidirectional spatial channel between island \( u \) and island \( v \) with an energy cost \( w_i \) for message transmission.

The next line contains \( N \) numbers, composed of 0 and 1, indicating whether the \( i \)-th island had a spatial storm at the city's founding. 0 means there was a storm, and 1 means there was no storm. We assume that if an island had no storm, it attracted residents; if it had a storm, no one lived there.

The last \( Q \) lines each describe an event, as follows:

\( 1 \ x \): For island \( x \), if there was no storm, a storm occurs, and all residents evacuate. Otherwise, the storm subsides, and residents return.

\( 2 \ x \ y \): Yuelingshuang asks a query about deploying Starkeeping Towers on the simple path from \( x \) to \( y \). The query asks for the minimum total energy consumption to transmit messages once to all inhabited islands. A Starkeeping Tower can transmit messages to multiple islands or none at all.

Output Format

Output \( Q \) lines, each containing a number representing the answer to that query.

Sample Input and Output

Input Sample #1

5 2 0
1 2 2
1 3 3
4 3 2
5 3 7
0 1 1 0 1
2 2 4
2 4 3

Output Sample #1

7
12

Input Sample #2

6 3 0
2 1 3
3 1 5
4 1 2
6 4 8
4 5 9
1 1 1 0 0 1
2 1 1
1 5
2 3 6

Output Sample #2

18
12

Notes/Hints

Special Property 1: \( v_i = u_i + 1 \)

Special Property 2: All queries have \( x \) and \( y \) the same.

Special Property 3: All queries have \( x = 1 \).

For all \( w_i \), it is guaranteed that \( 0 \leq w_i \leq 10^5 \).

For 100% of the data, it is guaranteed that \( n, m \leq 200000, 0 \leq Type \leq 7 \).

Sample 1 Explanation:

Initial diagram as shown on the left.

For the first query, as shown in the middle, islands 2, 3, and 5 have residents, so \( ans_2 = ans_3 = 0, ans_5 = 7 \). Thus, \( ans = 7 \).

For the second query, as shown on the right, \( ans_2 = 2 + 3 = 5, ans_3 = 0, ans_5 = 7 \), therefore \( ans = 7 + 5 = 12 \).

Sample 2 Explanation:

Initial diagram as shown on the top left.

Query for point 1 as shown on the top right, with islands 1, 2, 3, and 6 having residents. \( ans_1 = 0, ans_2 = 3, ans_3 = 5, ans_6 = 8 + 2 = 10 \). Thus, \( ans = 3 + 5 + 10 = 18 \).

After operation 1, all inhabited points are shown on the bottom left.

The next operation diagram is shown on the bottom right, with \( ans_1 = 0, ans_2 = 3, ans_3 = 0, ans_5 = 9, ans_6 = 0 \), so \( ans = 3 + 9 = 12 \).

见题面 Input 部分

见题面 Output 部分