Flipping Switches

You moved into a new home and the wiring is a mess. Several lights are controlled by several switches in a peculiar way. Every switch has two states, up and down. Calling them on and off is useless here. Each light is wired to three switches, and the light shines when at least one of those three is in its correct state. The opposite state of the same switch can be the correct state for another light.

Your first idea was to set the switches so that as many lights as possible shine. Your cook, who knows circuits, says that this is quite hard, so you settle for less. Find a setting in which flipping any single switch to its opposite state does not make more lights shine.

Several settings can satisfy that condition, so only the setting produced by the following procedure is accepted.

1. Put every switch up.
2. Scan the switches in order from 1 to $n$ and look for a switch whose flip, on its own, makes more lights shine than shine now.
3. If such a switch exists, flip the lowest numbered one and go back to step 2. If none exists, stop.

Each flip makes at least one more light shine, so the procedure always terminates.

The input contains several test cases.

The first line contains the number of test cases $t$ ($1 \le t \le 25$).

The first line of each test case contains the number of lights $m$ ($1 \le m \le 4000$) and the number of switches $n$ ($3 \le n \le 4000$). Line $i$ of the next $m$ lines contains three distinct integers $s_1$, $s_2$, $s_3$ ($1 \le s_i \le n$), each preceded by a + or a - character. These values are the switches that control light $i$ together with their correct states, where + means up and - means down.

For each test case, print on one line the switch setting produced by the procedure above. The setting is a string of $n$ characters, each + or -, where character $i$ is the state of switch $i$.