Question

Disney Land had an election on 1st April, 2018. Disney Land is divided into different constituencies.

Different parties who fought in the Election are as follows:-

Party 1 : AAA

Party 2 : BBB

Party 3 : Others

Disney Land is rolling out a new political process. Under this process, Disney Land will be divided into N * M equal parts called constituencies. These constituencies will then have to be aggregated into Political seats. The winner of the maximum number of seats will be the winner of the elections and will come to power in Disney Land.

The Aggregation process will involve distributing N*M constituencies into K Seats such that

Number of constituencies that are a part of a Electoral Seat is maximum i.e. of size B*B

No constituency is left out

There is no overlap of constituencies across Seats

Distribution of constituencies in Seats is equal

The party which wins maximum constituencies in a given Seat wins that Seat. Winner of maximum Seats wins the election.

For representational purpose, N*M constituencies of Disney Land are represented as a matrix. The winning political party in that constituency is represented with number as follows

Party AAA -> 1

Party BBB -> 2

Others -> 3

Given the matrix, find B*B different constituencies in the Disney Land (B < N, M). Find B in such a way that, B is maximum.

Unfortunate reality of Elections in this day and age is, Horse Trading. Disney Land is no different. After the election, some party may bribe some other party to surrender a particular constituency to win that seat.

Your task is to find which party won the Election after due process, including Horse-trading. If no party has a majority, then print "No Majority".

Constraints
Both N and M are even numbers

2<=N , M <=10

1<=seats <= 10

1<= H <= 10

Input Format
First Line indicates the Row (N) and Column (M) of the total number of constituencies in Disney Land.

Next N lines contain the data about which party has won which constituency

Next Line (After the N Lines of Seats) contains number of Horse-trades (H) that took place during the elections.

Next B Lines contains a data tuple where

X & Y are the row & column of the seat where bribe took place, and

Z is the Party who initiated the horse trading.

Output
First Line should contain the party who has the majority before horse-trading and the number of seats of that party, separated by a colon (:) or No Majority

Second Line should contain the party who has majority after horse-trading and the number of Seats of that party, separated by a colon (:) or No Majority

Answer 1

April fool. .............