Совсем недавно в Берляндии была построена новая дорожная сеть. Между некоторыми парами городов есть односторонние дороги, \(i\)-я из которых ведёт из города \(u_i\) в город \(v_i\), а её длина равна \(w_i\). Два главных города Берляндии имеют номера \(a\) и \(b\).

Король Берляндии очень любит свою страну. В частности, он обожает подсчитывать всякие характеристики в ней. Он называет красотой пути побитовое исключающее ИЛИ длин всех дорог на этом пути. А красотой своей страны он называет побитовое исключающее ИЛИ красот всех путей из города \(a\) в город \(b\). Обратите внимание, что таких путей может быть бесконечно много, и они могут проходить через один и тот же город несколько раз.

Король хочет узнать, чему равна красота его страны, а поэтому он обратился к вам за помощью и просит вас посчитать это значение или сказать, что красоту страны посчитать невозможно.

Побитовым исключающим ИЛИ множества чисел называется побитовое исключающее ИЛИ всех ненулевых чисел в этом множестве. Если в множестве бесконечно много ненулевых чисел, то побитовое исключающее ИЛИ посчитать невозможно.

Побитовое исключающее ИЛИ (или побитовое сложение по модулю два) — это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0. Например, если \(x = 109_{10} = 1101101_2\), а \(y = 41_{10} = 101001_2\), то их побитовое исключающее ИЛИ равно \(x \oplus y = 1000100_2 = 68_{10}\).

Путём в графе называется последовательность вершин, в которой любые две последовательные вершины соединены ребром.