8160 번 : Trains 
 8160 번 
 8160 번 - Trains 
 The Trains of Colour Parade begins tomorrow in Byteotia . Intense preparations are already in progress at the station ' s auxiliary tracks . There are n parallel tracks at the station , numbered from 1 to n . The train no . i occupies the ith track . Every train consists of l cars and each car is painted with one of 26 colours ( denoted by non - capital letters of the English alphabet ) . We say that two trains look the same , if their corresponding cars are painted the same colour . 
 Throughout the parade a crane will switch places of certain pairs of cars . The real parade , however , will take place tomorrow . Today the train dispatcher , Byteasar , watched the general rehearsal closely . He even wrote down the sequence of car swaps . 
 Byteasar particularly dislikes many trains looking the same . For each train p he would like to calculate the maximum number of trains that at some moment look the same as the train p at the very same moment . 
 reads descriptions of the trains occupying tracks and the sequence of car swaps , 
 for each train determines the maximum number of trains that look the same as it at certain moment , 
 writes out the result . 
 The first line of the input contains three integers n , l and m ( 2 ≤ n ≤ 1 , 000 , 1 ≤ l ≤ 100 , 0 ≤ m ≤ 100 , 000 ) , denoting respectively the number of trains , their common length and the number of car swaps . The following n lines contain descriptions of the trains on successive tracks . The kth line consists of l small letters of the English alphabet denoting the colours of successive cars of the kth train . Then m lines describing the car swaps follow , in the order of the swaps . The rth line contains four integers p 1 , w 1 , p 2 , w 2 ( 1 ≤ p 1 , p 2 ≤ n , 1 ≤ w 1 , w 2 ≤ l , p 1 ≠ p 2 or w 1 ≠ w 2 ) denoting the rth car swap - the car no . w 1 of the train no . p 1 is swapped with the car no . w 2 of the train no . p 2 . 
 Your programme should write out exactly n lines . The kth line should contain one integer - the number of trains looking the same as the train no . k at certain moment . 
 ababbd 
 abbbbd 
 caabbd 
 The figure presents the successive car swaps : 
 track 1 : ababbd ababbd ababbd ababbd aaabbd aaabbd aaabbd aaabbd 
 track 2 : abbbbd ababbd ababbd aaabbd aaabbd acabbd acabbd acabbd 
 track 3 : aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd 
 track 4 : caabbd caabbd caabbd caabbd cabbbd cabbbd cabbbd dabbbd 
 track 5 : cabaad cabbad caabbd caabbd caabbd aaabbd aaabbd aaabbc 
 The number of trains looking the same as either of the trains no . 1 , 2 or 3 was maximal at time ( 4 ) ( when all three looked the same ) . The number of trains looking the same as the train no . 5 was maximal at time ( 5 ) and ( 6 ) . The number of trains looking the same as the train no . 4 was maximal at time ( 2 ) . 
 Olympiad > Polish Olympiad in Informatics > POI 2007 / 2008 > Stage 2 3 번