Birzhan has cards, numbered from to . Every card has each number from to written on it. Some numbers exist on the front side of the card and some on the back side. No number exists on both the sides of a card at the same time. These cards are placed on the table in a row such that only one side is visible. Birzhan is allowed to flip them any number of times.
Now, Birzhan has to answer queries each of them consisting of two integers and (). We define as the sum of the squares of every integer from to if it exists on the visible side of any card numbered from to . Given that Birzhan can flip any number of cards any number of times, find and print the maximum value of .
For example, given cards and we have the as follows:-
Now, for and . We have on the two cards, the sum of their squares is .
If we flip the first card, we get , the sum of their squares is .
And, if we flip both cards, we get , the sum of their squares is
Hence, the maximum value of in the above case is .
The first line contains three space-separated integers, , , and , denoting the number of cards, what numbers written on each card, and the number of queries, respectively.
Each of the next lines describes the cards. On each line, the first number is , denoting the count of numbers written on the visible side of the card. Next space-separated unique integers represent the numbers written on the visible side of that card, each between and .
Next lines contain two space-separated integers, and , describing the query mentioned above.
Sample Input 0
2 3 2
Sample Output 0
In the first query, there is only card, and Birzhan has options:
- Let it be as it is: sum of squares would be
- Or flip it: sum of squares would be
So the maximum Birzhan can achieve is .
On the second query, Birzhan doesn’t need to flip any of them to maximize so the answer would be .
Sample Input 1
2 5 1
Sample Output 1
If Birzhan flipped only the first card, the answer would be . You can notice that it’s impossible to get a better result.