#777. 棋盘

棋盘

Description

给定一个n×n的棋盘,棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)能互相攻击当前仅

当满足以下两个条件:

1:x=u或y=v

2:对于(x,y)与(u,v)之间的所有位置,均不是障碍。

现在有q个询问,每个询问给定ki,要求从棋盘中选出ki个空位置来放棋子,问最少互相能攻击到的棋子对数是多少?

Format

Input

第一行一个整数n。

接下来输入一个n×n的字符矩阵,一个位置若为.,则表示这是一个空位置,若为#,则为障碍。

第n+2行输入一个整数q代表询问个数。

接下来q行,每行一个整数k,代表要放的棋子个数。

n ≤ 50, q ≤ 10000, k ≤ 棋盘中空位置数量

Output

输出共q行,每行代表对应询问的最少的互相能攻击到的棋子对数。

Samples

4
..#.
####
..#.
..#.
1 7
2