Maximum Custom Bitwise Spanning Tree

Given an undirected graph with n vertices and m edges. Each edge has a weight represented by a w-bit non-negative integer (i.e. less than \(2^w\)). We define three bitwise operations: \(\otimes_1\), \(\otimes_2\), and \(\otimes_3\), which correspond to bitwise AND, OR, and XOR respectively. Let \(a_i\) denote the \(i\)-th bit (from least significant to most significant) of the binary representation of an integer \(a\). A new operation \(\oplus\) is defined on w-bit numbers such that for each bit \(i\):

[ (a \oplus b)i = a_i \otimes{o_i} b_i, ]

Here, \(o_i \in \{1,2,3\}\) is provided as input and indicates which bitwise operator to use for the \(i\)-th bit. It is easy to verify that the \(\oplus\) operation is both associative and commutative.

You are given a graph and your task is to choose a spanning tree from the original graph. Let the weights of the selected spanning tree's edges be \(v_1, v_2, \dots, v_{n-1}\). Your goal is to maximize the value of

[ v_1 \oplus v_2 \oplus \cdots \oplus v_{n-1}. ]

inputFormat

The first line contains three integers \(n\), \(m\), and \(w\) -- the number of vertices, edges, and the number of bits, respectively.

The second line contains \(w\) integers: \(o_1, o_2, \dots, o_w\), where each \(o_i\) is either 1, 2, or 3. These indicate which bitwise operation to use for the corresponding bit (1 for AND, 2 for OR, 3 for XOR).

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(x\) representing an undirected edge connecting vertices \(u\) and \(v\) with weight \(x\) (with \(0 \le x < 2^w\)).

outputFormat

Output a single integer: the maximum possible value of \(v_1 \oplus v_2 \oplus \cdots \oplus v_{n-1}\) that can be achieved by choosing an appropriate spanning tree.

sample

3 3 3
3 3 3
1 2 1
2 3 2
1 3 3

3