Description

考虑一张 $n$ 个点的边带权无向图，点从 $1 \sim n$ 编号。对于图中的任意一个点集（可以为空集或是全集），称所有那些恰好有一个端点在这个点集中的边所组成的边集为割。

我们再定义一个割的权值为：这个割中所含的所有边边权的异或和。

现在初始时给定一张 $n$ 个点的空图，接下来会有若干次加（无向）边操作，每次加边后请你求出当前图中权值最大的割的权值。

Input Format

第一行两个整数 $n, m$ 表示图的点数与加入的总边数。

接下来 $m$ 行每行三个正整数 $x, y, w$ 表示加入一条连接 $(x, y)$ 的权值为 $w$ 的边。$x, y$ 可能相同，两点之间可能会有多条边。

$w$ 将会以二进制形式从高位到低位给出。

Output Format

输出 $m$ 行，按顺序给出每次加边后当前图中权值最大的割的权值。

权值也要以二进制形式输出，形式与输入格式中描述的一致。

Sample

样例输入

3 6
1 2 1
1 2 1
3 3 111
1 3 101101
1 2 1011
2 3 111011

样例输出

1
0
0
101101
101101
110000

Hint

对于所有数据：$ 1 \leq n \leq 500, 1 \leq m \leq 1000, 0 \leq l \leq 1000, 1 \leq x, y \leq n $