G. Nagham's Birthday
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad, being the bully he is, decided to gift Nagham this problem on her birthday (smh).

He gave her $$$n$$$ nodes and $$$m$$$ weighted edges, the starting node $$$s$$$, and the ending node $$$e$$$, and asked her to get the maximum possible value of a valid route, where the value of the route is the bitwise AND of weights on it.

You, being the good person you are, decided to help Nagham solve this problem. Will you be able to help her?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) – the number of test cases.

The first line of each test case contains four integers $$$n,m,s,e$$$ ($$$1 \leq s,e \leq 10^5$$$), ($$$2 \leq n \leq 10^5$$$), ($$$1 \leq m \leq 3\cdot10^5$$$).

The next $$$m$$$ lines contain $$$3$$$ numbers, the two nodes ($$$1\leq a,b \leq 10^5$$$) and the weight on the edge that connects them ($$$1 \leq w \lt 2^{60}$$$).

Output

For each test case, output the answer Ahmad is looking for.

Example
Input
3
4 4 1 3
1 4 8
1 2 12
4 3 40
2 3 16
3 4 1 3
1 2 32
2 3 32
1 2 64
2 3 8
3 3 2 3
1 2 4
1 3 8
1 3 12
Output
8
32
4