题目描述

给定一个 $n \times n$ 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 $(x, y),(u, v)$ 能互相攻击当前仅当满足以下两个条件：

• $x = u$ 或 $y = v$
• 对于 $(x, y)$ 与 $(u, v)$ 之间的所有位置，均不是障碍。 现在有 $q$ 个询问，每个询问给定 $k_i$，要求从棋盘中选出 $k_i$ 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？

输入格式

第一行一个整数 $n$。

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

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

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

输出格式

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

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

2

提示

对于 $20\%$ 的数据，$n \leq 5$；

对于 $40\%$ 的数据，$n \leq 10$；

另外有 $20\%$ 的数据，$q = 1$；

对于 $100\%$ 的数据，$n \leq 50; q \leq 10000; k \leq$ 棋盘中空位置数量。