Valera the Horse is going to the party with friends. He has been following the fashion trends for a while, and he knows that it is very popular to wear all horseshoes of different color. Valera has got four horseshoes left from the last year, but maybe some of them have the same color. In this case he needs to go to the store and buy some few more horseshoes, not to lose face in front of his stylish comrades.

Fortunately, the store sells horseshoes of all colors under the sun and Valera has enough money to buy any four of them. However, in order to save the money, he would like to spend as little money as possible, so you need to help Valera and determine what is the minimum number of horseshoes he needs to buy to wear four horseshoes of different colors to a party.

You've got two rectangular tables with sizes n_a × m_a and n_b × m_b cells. The tables consist of zeroes and ones. We will consider the rows and columns of both tables indexed starting from 1. Then we will define the element of the first table, located at the intersection of the i-th row and the j-th column, as a_i, j; we will define the element of the second table, located at the intersection of the i-th row and the j-th column, as b_i, j.

We will call the pair of integers (x, y) a shift of the second table relative to the first one. We'll call the overlap factor of the shift (x, y) value:

where the variables i, j take only such values, in which the expression a_i, j·b_{i + x, j + y} makes sense. More formally, inequalities 1 ≤ i ≤ n_a, 1 ≤ j ≤ m_a, 1 ≤ i + x ≤ n_b, 1 ≤ j + y ≤ m_b must hold. If there are no values of variables i, j, that satisfy the given inequalities, the value of the sum is considered equal to 0.

Your task is to find the shift with the maximum overlap factor among all possible shifts.

Little Vasya likes painting fractals very much.

He does it like this. First the boy cuts out a 2 × 2-cell square out of squared paper. Then he paints some cells black. The boy calls the cut out square a fractal pattern. Then he takes a clean square sheet of paper and paints a fractal by the following algorithm:

1. He divides the sheet into four identical squares. A part of them is painted black according to the fractal pattern.
2. Each square that remained white, is split into 4 lesser white squares, some of them are painted according to the fractal pattern. Each square that remained black, is split into 4 lesser black squares.

In each of the following steps step 2 repeats. To draw a fractal, the boy can make an arbitrary positive number of steps of the algorithm. But he need to make at least two steps. In other words step 2 of the algorithm must be done at least once. The resulting picture (the square with painted cells) will be a fractal. The figure below shows drawing a fractal (here boy made three steps of the algorithm).

One evening Vasya got very tired, so he didn't paint the fractal, he just took a sheet of paper, painted a n × m-cell field. Then Vasya paint some cells black.

Now he wonders, how many squares are on the field, such that there is a fractal, which can be obtained as described above, and which is equal to that square. Square is considered equal to some fractal if they consist of the same amount of elementary not divided cells and for each elementary cell of the square corresponding elementary cell of the fractal have the same color.

The court wizard Zigzag wants to become a famous mathematician. For that, he needs his own theorem, like the Cauchy theorem, or his sum, like the Minkowski sum. But most of all he wants to have his sequence, like the Fibonacci sequence, and his function, like the Euler's totient function.

The Zigag's sequence with the zigzag factor z is an infinite sequence S_i^z (i ≥ 1; z ≥ 2), that is determined as follows:

• S_i^z = 2, when ;
• , when ;
• , when .

Operation means taking the remainder from dividing number x by number y. For example, the beginning of sequence S_i³ (zigzag factor 3) looks as follows: 1, 2, 3, 2, 1, 2, 3, 2, 1.

Let's assume that we are given an array a, consisting of n integers. Let's define element number i (1 ≤ i ≤ n) of the array as a_i. The Zigzag function is function , where l, r, z satisfy the inequalities 1 ≤ l ≤ r ≤ n, z ≥ 2.

To become better acquainted with the Zigzag sequence and the Zigzag function, the wizard offers you to implement the following operations on the given array a.

1. The assignment operation. The operation parameters are (p, v). The operation denotes assigning value v to the p-th array element. After the operation is applied, the value of the array element a_p equals v.
2. The Zigzag operation. The operation parameters are (l, r, z). The operation denotes calculating the Zigzag function Z(l, r, z).

Explore the magical powers of zigzags, implement the described operations.

Berland has n cities, some of them are connected by bidirectional roads. For each road we know whether it is asphalted or not.

The King of Berland Valera II wants to asphalt all roads of Berland, for that he gathered a group of workers. Every day Valera chooses exactly one city and orders the crew to asphalt all roads that come from the city. The valiant crew fulfilled the King's order in a day, then workers went home.

Unfortunately, not everything is as great as Valera II would like. The main part of the group were gastarbeiters — illegal immigrants who are enthusiastic but not exactly good at understanding orders in Berlandian. Therefore, having received orders to asphalt the roads coming from some of the city, the group asphalted all non-asphalted roads coming from the city, and vice versa, took the asphalt from the roads that had it.

Upon learning of this progress, Valera II was very upset, but since it was too late to change anything, he asked you to make a program that determines whether you can in some way asphalt Berlandian roads in at most n days. Help the king.