The link to the Russian translation.

On the way to kill one of vampires Reyna addressed, Damon and Enzo arrive at a mysterious town. This town has n intersections and m one-way roads. Each road has a length and a character written on it! This character is either a '(' or ')'.

This town is mysterious because in it, a route (may pass a road more than once) is proper (one can kill vampires at the end of it) iff when we write down the characters on the roads one by one, it forms a correct bracket sequence.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence

Damon and Enzo want to know for each two intersections s and t, the length of the shortest proper route from s to t (It may not exist, also for s = t answer is 0 since "" is a correct bracket sequence due to the definition).

They are really pissed off right now, so you better answer them ;)

Input

The first line of input contains two integers n and m (1 ≤ n ≤ 300, 1 ≤ m ≤ min(80000, n×(n-1))).

The next m lines contain the roads. Each line contains three integers v, u, w and a character c (either ( or )) meaning there is a road from *v to u with length w written c on it (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ w ≤ 10⁹). It's guaranteed that there is at most one road from v to u.

Output

Your output should be a n by n matrix (numbers in each line should be space-separated). j-th cell in i-th row should contain the length of the shortest proper route from i to j if there exists such route, or -1 otherwise.