The Trains of Colour Parade

In Byteotia the festive Trains of Colour Parade is about to begin! There are $n$ parallel tracks at the station, numbered from $1$ to $n$. Train $i$ occupies track $i$, and each train consists of $l$ cars. Every car is painted with one of 26 colours (denoted by lowercase letters of the English alphabet). Two trains are said to look the same if their corresponding cars are painted with the same colour.

During the rehearsal, a crane swapped the positions of certain pairs of cars. Each swap operation is described by four integers $a$, $p$, $b$, $q$, meaning that the car at position $p$ of train $a$ is swapped with the car at position $q$ of train $b$. All indices are 1-indexed. Note that these swaps might exchange cars between different trains, thereby changing the appearance of the trains.

For each train $p$, Byteasar would like to know the maximum number of trains that, at some moment in time (including the initial configuration and after any swap), have looked the same as train $p$. Write a programme to compute this value for every train based on the initial configurations and the given sequence of swaps.

inputFormat

The first line contains two integers $n$ and $m$, where $n$ is the number of trains and $m$ is the number of swap operations. Each of the following $n$ lines contains a string of length $l$, representing the colours of the cars in a train.

Each of the following $m$ lines contains four integers $a$, $p$, $b$, $q$, indicating that the car in position $p$ of train $a$ is swapped with the car in position $q$ of train $b$. (All indices are 1-indexed.)

outputFormat

Output a single line containing $n$ integers separated by spaces. The $i$-th integer is the maximum number of trains that looked identical to train $i$ at the same moment in time (considering the initial configuration and the state after every swap operation).

sample

3 2
abc
abc
acb
1 2 3 2
2 3 3 3

2 2 1