BitMania es una ciudad con \(n\) intersecciones y \(m\) calles. Cada calle conecta dos intersecciones y tiene asociado un número entero que representa su longitud.
Un recorrido en la ciudad es una secuencia de intersecciones y calles tal que cada calle conecta la intersección anterior con la siguiente. Es importante notar que un recorrido puede pasar por la misma intersección o calle más de una vez.
Gracias a una revolucionaria tecnología que se está experimentando en la ciudad, el costo de un recorrido se define como el AND bit a bit de las longitudes de todas las calles recorridas. Es decir, si el recorrido atraviesa calles con longitudes \(c_1\), \(c_2\), ..., \(c_k\), su costo es: \(c_1\) \(\&\) \(c_2\) \(\&\) \(...\) \(\&\) \(c_k\).
Se te dan \(q\) consultas. Cada consulta consiste en un par de intersecciones (\(u, v\)), y debes determinar el costo mínimo posible de cualquier recorrido que comience en \(u\) y termine en \(v\), o determinar que no existe ningún camino entre ambas intersecciones.
Entrada
La primera línea contiene dos enteros \(n\) y \(m\), que representan el número de intersecciones y calles, respectivamente (\(1 \le n \le 2 \cdot 10^5\), \(0 \le m \le 2 \cdot n\)).
Las siguientes \(m\) líneas contienen tres enteros \(u\), \(v\) y \(c\), indicando que existe una calle entre las intersecciones \(u\) y \(v\) con longitud \(c\) (\(1 \le u, v \le n\), \(0 \le c \le 2 \cdot 10^5\)).
La siguiente línea contiene un entero \(q\), indicando el número de consultas (\(1 \le q \le 2 \cdot 10^5\)).
Las siguientes \(q\) líneas contienen dos enteros \(u\) y \(v\), indicando las intersecciones que conforman la consulta.
Salida
Para cada consulta, imprime en una línea distinta el costo mínimo de cualquier recorrido que conecte \(u\) con \(v\). Si no existe ningún recorrido posible, imprime -1.