Description

Cat City has $n$ markets, connected by $n-1$ bidirectional roads such that any two markets can reach each other via some paths. Each market sells two types of goods $a_u, b_u$ ($a_u \neq b_u$).

Now Xiao Meng, a cat, has planned $Q$ journeys. Each time, Xiao Meng will start from market $u$ and travel along the shortest path to market $v$.

When passing through a market (including $u$ and $v$), Xiao Meng will attempt to trade. If Xiao Meng already possesses one of the goods sold at that market, he will exchange it for the other good sold there; otherwise, he keeps his original goods.

Initially, Xiao Meng possesses a good of type $x$. Find out what type of good Xiao Meng ends up with after the journey.

Input Format

The first line contains two positive integers $n, Q$.

The next two lines each contain $n$ positive integers. The $i$-th number in the first line is $a_i$, and the $i$-th number in the second line is $b_i$.

The following $n-1$ lines each contain two positive integers $u, v$, indicating a road between market $u$ and market $v$.

The following $Q$ lines each contain three positive integers $u, v, x$, describing a journey.

Output Format

Output $Q$ lines, each containing a positive integer representing the type of good Xiao Meng finally possesses.

5 3
3 4 1 5 2
2 5 5 2 4
5 4
1 4
3 1
2 4
3 4 1
2 5 4
1 5 3

2
4
5

Hint

This problem uses bundled testing.

::cute-table{tuack} | Subtask | Constraints | Special Properties | Points | |:---------:|:---------------:|:----------------------:|:-----:| | Subtask 1 | $N,Q \leq 1000$ | The tree is a chain | 5 | | Subtask 2 | $N,Q \leq 1000$ | None | 15 | | Subtask 3 | $N,Q \leq 10^6$ | $\forall i, a_i=1, b_i=2$ | 10 | | Subtask 4 | $N,Q \leq 10^6$ | The tree is a chain | 15 | | Subtask 5 | $N,Q \leq 10^5$ | None | 25 | | Subtask 6 | $N,Q \leq 10^6$ | None | 30 |

For $100\%$ of the data, $2 \le N \le 10^6$, $1 \le Q \le 10^6$, $1 \le a_i, b_i \le N$.

Please pay special attention to the time and memory limits.

Explanation of Example 1

As shown in the figure, for the first query: starting from market $3$, because Xiao Meng possesses good $1$, he exchanges it for $5$. At market $2$, there is no matching good, so no exchange occurs. At market $4$, he exchanges it for good $2$.

A Fast I/O Template Is Provided

namespace io
{
	char *p1,*p2,buf[100001];
	#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
	template<typename T>
	inline typename __gnu_cxx::__enable_if<__is_integer<T>::__value,T>::__type read()
	{
		T sum=0;
		char ch;
		do ch=getchar();                               while(!isdigit(ch));
		do sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); while( isdigit(ch));
		return sum;
	}
	template<typename T>
	inline typename __gnu_cxx::__enable_if<__is_integer<T>::__value,void>::__type read(T& sum)
	{
		sum=0;
		char ch;
		do ch=getchar();                               while(!isdigit(ch));
		do sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); while( isdigit(ch));
	}
	#undef getchar
}

Usage

int n;
long long m;
io::read(n);
io::read(m);
int k = io::read<int>();
long long q = io::read<long long>();