Background

That year, you and I were still flawless teenagers.

In the quiet backyard at night, we laughed and talked about life without any worries.

— Missing those days with no suspicion at all.

Problem Description

Yue, Ling, and Ying are wandering in the City at the Bottom of the Lake. The roads there are complicated and form a tree with $n$ nodes.

Each of them has a counter, all starting at $0$. Whenever they arrive at a node, Yue and Ying’s counters will automatically increase by the weight of the edge they just walked through, while Ling’s counter will increase by exactly $1$. Also, during the whole process, they never pass through any node more than once.

Because their counters cannot store very large values, when Ling’s counter is a multiple of the “Lake Number” $p$, Yue may subtract the value of Ying’s counter from her own counter, and then Ling and Ying’s counters will both be reset to zero immediately.

Qi does not know their starting point and ending point, so for every pair of start and end nodes, the naturally strong-at-calculation Qi computed the minimum possible value that could appear on Yue’s counter at the ending node. Qi denotes this value as $f(u,v)$, meaning they walked from node $u$ to node $v$. However, Qi believes that without the red spider lily, Han surely cannot compute these answers. So he asks Han to solve an easier problem. Qi gives Han a sequence $s$ of length $m$, and asks Han to compute $\min\limits_{i=1}^m\{f(s_i,u)\}$ for every node $u$.

Formal Statement

Given a tree $(V,E)$ with $n$ nodes and a positive integer $p$. Each edge has an integer weight $w_i$.

We define $f(s,v)$ as the minimum value of $a$ when $u=v$ that can be obtained after performing the operation extension several times on $u,a,b,c$, where initially $u\gets s$ and $a,b,c\gets0$.

An extension is defined as performing the following operations in order:

• Choose any edge $(u',v,w)\in E$ such that $u=u'$, then set $u\gets v,a\gets a+w,b\gets b+1,c\gets c+w$;

• If $p\mid b$, you may set $a\gets a-c,b\gets 0,c\gets0$.

In particular, in each extension, you cannot choose a node that has been chosen before.

Given the sequence $\{s_m\}$, for every node $u$, find $\min\limits_{i=1}^m\{f(s_i,u)\}$.

Input Format

The first line contains three integers $n,m,p$, meaning the tree has $n$ nodes labeled $1\sim n$, the “Lake Number” is $p$, and the length of sequence $s$ is $m$.

The next $n-1$ lines each contain three integers $u,v,w$, meaning there is an edge connecting nodes $u$ and $v$ with weight $w$.

The next line contains $m$ integers representing $s_{1\sim m}$, i.e. the $m$ starting nodes.

Output Format

Let $ans_u=\min\limits_{i=1}^m\{f(s_i,u)\}$. You need to output $\text{xor}_{i=1}^n |ans_i|$, where $|a|$ denotes the absolute value of $a$.

6 2 2
1 2 -2
1 3 1
1 4 2
2 5 -3
2 6 10
1 5

4

Hint

Sample Explanation

• If they start from node $1$, first we have $f(1,1)=0$. When they walk to nodes $2,3,4$, the values on Yue’s counter are $-2,1,2$ respectively, so $f(1,2)=-2,f(1,3)=1,f(1,4)=2$. When they walk to nodes $5,6$, the values on Yue’s counter are $-5,8$ respectively. Since Ling’s counter is $2$ at this time, which is a multiple of $p$, Yue may choose to subtract Ying’s counter from her counter. It is not hard to get $f(1,5)=-5,f(1,6)=0$.

• If they start from node $5$, similarly we can get $f(5,5)=0,f(5,2)=-3,f(5,6)=0,f(5,1)=-5,f(5,4)=-3,f(5,3)=-4$.

Therefore, $\{ans_n\}=\{-5,-3,-4,-3,-5,0\}$. We can compute that $\text{xor}_{i=1}^n |ans_i|=4$.

Constraints

This problem uses bundled testdata.

Special property: it is guaranteed that the tree degenerates into a chain.

For $100\%$ of the data, $1\le m\le n\le10^5$, $1\le p\le100$, $-10^4\le w\le10^4$, $1\le u,v,s_i\le n$.

Translated by ChatGPT 5