Description

Define $\otimes_1, \otimes_2, \otimes_3$ as bitwise AND, bitwise OR, and bitwise XOR, respectively. Let $a_i$ denote the $i$-th binary bit of $a$ from low to high. Define a new operation $\oplus$ on $w$-bit binary numbers such that for each bit $(a\oplus b)_i$ of the result $a\oplus b$, we have $(a\oplus b)_i = a_i \otimes_{o_i} b_i$. It is not hard to verify that the operation $\oplus$ is associative and commutative.

Given an undirected graph with $n$ vertices and $m$ edges, each edge weight is a $w$-bit binary number (i.e., a non-negative integer less than $2^w$). Please find a spanning tree of the original graph. Suppose the edge weights in your spanning tree are $v_1,\cdots,v_{n-1}$. Please maximize $v_1\oplus v_2\oplus\cdots\oplus v_{n-1}$.

Input Format

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

The second line contains a string of length $w$. Each character in the string is one of &, |, ^ (representing AND, OR, XOR, respectively), indicating each $\otimes_{o_i}$.

The next $m$ lines each contain three non-negative integers $x,y,v$, representing an edge connecting $x$ and $y$ with weight $v$. It is guaranteed that $1\leq x,y\leq n$, $0\le v < 2^w$.

For all testdata, $1\le n\le 70,1\le m\le 5000,1\le w \le 12$.

Output Format

Output one line with one number, indicating the answer. If the graph is disconnected, output -1.

3 3
^
1 2 1
2 3 1
1 3 0

1

Hint

About the testdata

For some reasons, the testdata only keeps the last $20$ vertices.

Copyright information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as solutions can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5