ZOJ Problem Set - 3354
Global warming affects the whole world right now. DoIt is a country which is surrounded by the sea and suffering from global warming. Scientists in DoIt find out that the sea level will rise 1 meter every year so that some places in DoIt will be flooded and disappear from the earth. As a result, the country may be divided into several islands and finally disappear.
DoIt's government wants to know how much it can earn before the whole country's disappearance. Thanks for economists, its income can be decided by the size of unflooded places and an economic coefficient A. A will change with years and it has been well forecasted by economists. The total income of DoIt is the sum of all islands' income. For each island, its income equals 2 Bits(S & A). S is the size of the island and A is the economic coefficient of that year. Bits(x) means the number of 1 in x's binary code.
Assuming DoIt can be represented by n * m grids, an integer in a grid indicates its altitude. The size of a grid is 1. Two grids are adjacent if they have a common edge. Note that, water in a grid can only flow into grids which are adjacent to the current grid. At first, it's year 0 and the sea level is 0. Therefore, in the d-th year, the sea level will rise to d at the very begining of the year. There are several queries asked by the government. Each query includes two integers, d, A, representing the year and the economic coefficient of that year. You should output DoIt's total income in the d-th year. You can assume that the sea level changes at the beginning of the year and keeps unchanged in that year. So the total income is caclulated after this change.
There are multiple test cases (about 10).
For each case, in the first line there are two integers n and m (1 ≤ n, m ≤ 500). Then in the next n lines, each line has m integers. It's guaranteed that all altitudes are larger than 0 and no more than 1000000.
After that, there is an integer Q (1 ≤ Q ≤ 10000), representing the number of queries. In the next Q lines, each line has two integers, d (1 ≤ d ≤ 1000000) and A (0 ≤ A ≤ 1000000000). It's possible that different economic coefficients are found in the same year.
For each query, output the total income of DoIt in that year.
5 5 6 6 6 6 8 5 2 2 2 5 5 2 3 2 4 8 2 1 1 5 7 4 5 5 5 4 3 255 5 255 7 255 9 255
8 6 4 0
Because of the large input, scanf is recommended.
Author: MO, Luyi
Source: ZOJ Monthly, July 2010