In the kingdom of Absurdistan there are N airports, and in the far away country of Utopia there are M airports.
Currently, there is no air traffic on any of these airports.
Each airport has some capacity - i.e., a limit on the number of flights it can handle. Capacities may be different for different airports.
The citizens of the two countries would like to connect them by new flights. The schedule must follow these rules:
- Each flight is a two-way service that directly connects an airport in Absurdistan and an airport in Utopia.
- No pair of airports can be connected by more than one flight.
- Together, the flights must exactly meet the capacities of all airports. That is, for each airport the number of flights scheduled from it to another airports must be exactly the same as the capacity for this airport.
- If there are multiple schedules that satisfy the previous rules, the lexicographically smallest one (definition follows) must be chosen.
Each possible schedule can be represented as a matrix with N rows and M columns.
The rows correspond to airports in Absurdistan (in alphabetical order), the columns to airports in Utopia (again, in alphabetical order).
The cell at (r,c) contains the number 1 if the two airports are connected by a flight and 0 otherwise.
To compare two schedules, find the first row in which they differ, and in that row find the first column in which they differ.
The one that contains a zero in this cell is lexicographically smaller.
You are given two ints: capacityA and capacityU. The int capacityA contains the capacities of all the airports in Absurdistan in alphabetical order. The int capacityU describes the Utopian airports in the same way.
If there is no valid schedule, return an empty String. Otherwise, find the lexicographically smallest valid schedule and return it formatted as a String.