Description

Patrick is a student in the prgramming course. After he solved the problem 12964 - Sierpiński carpet, he creates a pattern similar to Sierpinski carpet and name it as Patrick Star carpet because his name is Patrick and he is a star fish.

Patrick Star carpet is a square that its side length is the power of 3 and all the grids are coloerd white. The construction is described as follow.

For a Patrick Star carpet that its side length is three, color the 4 corner and the center one with black. For a Patrick star carpet with side length greater than 3, cut it into 9 congruent subsquares in a 3-by-3 grid, and then apply the same procedure to the subsquare at the four corner and the center, that is, put a Patrick Star carpet that its side length is the one-third of the original side length in the subsquares at the four corner and the center.  

For instance, the following figures are the Patrick Star carpet with side length 3 and 9.

The following fugure is the Patrick Star carpet with side length 27.

Input

Input contains only one line with single integer n (1 <= n <= 7).

Output

Output the Patrick Star carpet with side length 3ⁿ and use '.' to represent white, '#' to represent black.
Remember to add a newline character at the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The only difference between easy and hard versions are constraints on q, a_i and b_i.

There are n items. The weight and value of the i-th item are w_i and v_i separately.

The total weight of items you can take away is at most m.

There are q queries. In each query, what is the maximum sum of value you can get if you must take the a_i-th item and b_i-th item?

Input

The first line contains two integers n, m (2 ≤ n ≤ 20, 0 ≤ m ≤ 10⁹) – the number of items and the totol weight you can take away.

Then n lines follow. The i+1-th line contains two integers w_i, v_i (0 ≤ w_i, v_i ≤ 10⁹) – the weight and value of the i-th item.

Next line contains one integer q (q = 1) – the times of the queries.

Then q lines follow. The i+n+2-th line contains two integers a_i, b_i (1 ≤ a_i < b_i ≤ n) – the two items you must take in the i-th query. It is guaranteed that the weight and value of both the a_i-th item and the b_i-th item must be zero.

Output

For each query output the maximum sum of value you can get(if there is no legal plan, output 0 instead) and then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The only difference between easy and hard versions are constraints on q, a_i and b_i.

There are n items. The weight and value of the i-th item are w_i and v_i separately.

The total weight of items you can take away is at most m.

There are q queries. In each query, what is the maximum sum of value you can get if you must take the a_i-th item and b_i-th item?

Input

The first line contains two integers n, m (2 ≤ n ≤ 20, 0 ≤ m ≤ 10⁹) – the number of items and the totol weight you can take away.

Then n lines follow. The i+1-th line contains two integers w_i, v_i (0 ≤ w_i, v_i ≤ 10⁹) – the weight and value of the i-th item.

Next line contains one integer q (1 ≤ q ≤ 10⁵) – the times of the queries.

Then q lines follow. The i+n+2-th line contains two integers a_i, b_i (1 ≤ a_i < b_i ≤ n) – the two items you must take in the i-th query.

Output

For each query output the maximum sum of value you can get(if there is no legal plan, output 0 instead) and then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss