Tenka1 Programmer Contest - Equilateral

There are some coins in the xy-plane. The positions of the coins are represented by a grid of characters with H rows and W columns. If the character at the i-th row and j-th column, s_{ij}, is `#`, there is one coin at point (i,j); if that character is `.`, there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

* Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.



Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

* 1 \leq H,W \leq 300
* s_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}


Output

Print the number of triples that satisfy the condition.

Examples

Input

5 4
#.##
.##.
#...
..##
...#


Output

3


Input

5 4
.##
.##.
...
..##
...#


Output

3


Input

13 27
......#.........#.......#..
...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
.#.#.#...###..
...........#...#...#######
..#######..#...#...#.....#
..#.....#..#...#...#.###.#
..#######..#...#...#.#.#.#
..........##...#...#.#####


Output

870

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(H, W) = map(int, input().split())
S = [list(input()) for i in range(H)]
table = [[0] * (H + W - 1) for i in range(H + W - 1)]
for j in range(H):
	for i in range(W):
		if S[j][i] == '#':
			table[i + j][i - j + H - 1] = 1
yoko = [[0] * (H + W) for i in range(H + W - 1)]
for j in range(H + W - 1):
	for i in range(1, H + W):
		yoko[j][i] = yoko[j][i - 1] + table[j][i - 1]
tate = [[0] * (H + W - 1) for i in range(H + W)]
for j in range(1, H + W):
	for i in range(H + W - 1):
		tate[j][i] = tate[j - 1][i] + table[j - 1][i]
ans = 0
for y in range(H + W - 1):
	for x in range((y + H - 1) % 2, H + W - 1, 2):
		if table[y][x] != 1:
			continue
		for z in range(x + 2, H + W - 1, 2):
			if table[y][z] == 1:
				d = z - x
				if y + d < H + W - 1:
					ans += yoko[y + d][z + 1] - yoko[y + d][x]
				if y - d >= 0:
					ans += yoko[y - d][z + 1] - yoko[y - d][x]
		for w in range(y + 2, H + W - 1, 2):
			if table[w][x] == 1:
				e = w - y
				if x + e < H + W - 1:
					ans += tate[w][x + e] - tate[y + 1][x + e]
				if x - e >= 0:
					ans += tate[w][x - e] - tate[y + 1][x - e]
print(ans)


(H, W) = map(int, input().split())
I = [input() for _ in range(H)]
X = [[[0, 1][a == '#'] for a in inp] for inp in I]
k = 32

def r():
	global H, W, I
	I = [''.join([I[H - 1 - j][i] for j in range(H)]) for i in range(W)]
	(H, W) = (W, H)

def st1(s):
	return int(s.replace('#', '1' * k).replace('.', '0' * k), 2)

def st2(s):
	return int(s.replace('#', '0' * (k - 1) + '1').replace('.', '0' * k), 2)

def getsum(x):
	for i in range(8):
		x += x >> (k << i)
	return x & (1 << k) - 1
ans = 0
for _ in range(4):
	A1 = [st1(inp) for inp in I]
	A2 = [st1(''.join([I[i][j] for i in range(H)])) for j in range(W)]
	B = [st2(inp[::-1]) for (i, inp) in enumerate(I)]
	C = [[0] * W for _ in range(H)]
	for j in range(W):
		s = 0
		m = (1 << j * k) - 1
		for i in range(H)[::-1]:
			s <<= k
			s += B[i] >> (j + 1) * k
			s &= m
			C[i][j] = s
	for i in range(1, H):
		for j in range(1, W):
			ans += A1[i] >> (W - j) * k & A2[j] >> (H - i) * k & C[i][j]
	r()
print(getsum(ans))


from itertools import accumulate
(h, w) = map(int, input().split())
field = [input() for _ in range(h)]
l = max(h, w)
precalc_rd = []
precalc_ld = []
for ij in range(h + w - 1):
	coins = [0] * (l + 1)
	min_i = max(0, ij - w + 1)
	max_i = ij - max(0, ij - h + 1)
	offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
	for d in range(max_i - min_i + 1):
		i = min_i + d
		j = ij - i
		if field[i][j] == '#':
			coins[offset + d] = 1
	precalc_ld.append(list(accumulate(coins)))
for ij in range(-w + 1, h):
	coins = [0] * (l + 1)
	min_i = max(0, ij)
	max_i = ij + min(w - 1, h - ij - 1)
	offset = (min_i + (min_i - ij)) // 2 + 1
	for d in range(max_i - min_i + 1):
		i = min_i + d
		j = i - ij
		if field[i][j] == '#':
			coins[offset + d] = 1
	precalc_rd.append(list(accumulate(coins)))
ans = 0
for ij in range(h + w - 1):
	min_i = max(0, ij - w + 1)
	max_i = ij - max(0, ij - h + 1)
	offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
	for sd in range(max_i - min_i + 1):
		si = min_i + sd
		sj = ij - si
		if field[si][sj] == '.':
			continue
		for td in range(sd + 1, max_i - min_i + 1):
			ti = min_i + td
			tj = ij - ti
			if field[ti][tj] == '.':
				continue
			dij = (td - sd) * 2
			if ij - dij >= 0:
				ans += precalc_ld[ij - dij][offset + td - 1] - precalc_ld[ij - dij][offset + sd - 1]
			if ij + dij <= h + w - 2:
				ans += precalc_ld[ij + dij][offset + td] - precalc_ld[ij + dij][offset + sd]
for ij in range(-w + 1, h):
	min_i = max(0, ij)
	max_i = ij + min(w - 1, h - ij - 1)
	offset = (min_i + (min_i - ij)) // 2 + 1
	for sd in range(max_i - min_i + 1):
		si = min_i + sd
		sj = si - ij
		if field[si][sj] == '.':
			continue
		for td in range(sd + 1, max_i - min_i + 1):
			ti = min_i + td
			tj = ti - ij
			if field[ti][tj] == '.':
				continue
			dij = (td - sd) * 2
			if ij - dij + w - 1 >= 0:
				ans += precalc_rd[ij - dij + w - 1][offset + td] - precalc_rd[ij - dij + w - 1][offset + sd]
			if ij + dij + w - 1 <= h + w - 2:
				ans += precalc_rd[ij + dij + w - 1][offset + td - 1] - precalc_rd[ij + dij + w - 1][offset + sd - 1]
print(ans)


(H, W) = map(int, input().split())
src = [input() for i in range(H)]

def solve():
	cums = [[0] * (H + W) for y in range(H + W - 1)]
	coins = [[] for y in range(H + W - 1)]
	for i in range(H):
		for j in range(W):
			if src[i][j] == '.':
				continue
			(x, y) = (j - i + H, j + i)
			cums[y][x] += 1
			coins[y].append(x)
	for i in range(H + W - 1):
		for j in range(H + W - 1):
			cums[i][j + 1] += cums[i][j]
	cnt = 0
	for y1 in range(H + W - 1):
		if len(coins[y1]) < 2:
			continue
		for i1 in range(len(coins[y1]) - 1):
			for i2 in range(i1 + 1, len(coins[y1])):
				(x1, x2) = (coins[y1][-1 - i1], coins[y1][-1 - i2])
				y2 = y1 - (x2 - x1)
				if y2 < 0:
					continue
				cnt += cums[y2][x2] - cums[y2][x1]
	return cnt

def rotate():
	global H, W, src
	(H, W) = (W, H)
	src2 = []
	for col in reversed(list(zip(*src))):
		src2.append(''.join(list(col)))
	src = src2
ans = 0
for i in range(4):
	rotate()
	ans += solve()
print(ans)


import sys
input = sys.stdin.readline

class CumulativeSum2D:

	def __init__(self, field):
		self.h = len(field)
		self.w = len(field[0])
		self.h_offset = self.h
		self.w_offset = self.w
		self.field = field
		self.cumsum = [[0] * (self.w + self.w_offset * 2) for _ in range(self.h_offset)]
		for line in self.field:
			self.cumsum.append([0] * self.w_offset + line + [0] * self.w_offset)
		for i in range(self.h_offset):
			self.cumsum.append([0] * (self.w + self.w_offset * 2))

	def calc_diagonal_cumsum(self):
		for h in range(self.h_offset, self.h_offset + self.h):
			delta = 1
			while delta + h < self.h_offset * 2 + self.h and self.w_offset + delta < self.w_offset * 2 + self.w:
				self.cumsum[h + delta][self.w_offset + delta] += self.cumsum[h + delta - 1][self.w_offset + delta - 1]
				delta += 1
		for w in range(self.w_offset + 1, self.w_offset + self.w):
			delta = 1
			while delta + w < self.w_offset * 2 + self.w and self.h_offset + delta < self.h_offset * 2 + self.h:
				self.cumsum[self.h_offset + delta][w + delta] += self.cumsum[self.h_offset + delta - 1][w + delta - 1]
				delta += 1

	def get_diagonal_sum(self, x1, y1, x2, y2):
		ret = self.cumsum[y2 + self.h_offset][x2 + self.w_offset]
		ret -= self.cumsum[y1 - 1 + self.h_offset][x1 - 1 + self.w_offset]
		return ret

def rotate(field):
	h = len(field)
	w = len(field[0])
	(h, w) = (w, h)
	new_field = []
	for col in zip(*field):
		new_field.append(list(reversed(col)))
	return new_field
(n, m) = [int(item) for item in input().split()]
field = [[0] * m for _ in range(n)]
for i in range(n):
	line = input().rstrip()
	for j in range(m):
		if line[j] == '#':
			field[i][j] = 1
ans = 0
for i in range(4):
	n = len(field)
	m = len(field[0])
	cs = CumulativeSum2D(field)
	cs.calc_diagonal_cumsum()
	lu_to_rd = [[] for _ in range(n + m - 1)]
	for i in range(m):
		x = i
		y = 0
		delta = 0
		while x + delta < m and y + delta < n:
			if field[y + delta][x + delta] == 1:
				lu_to_rd[i].append((x + delta, y + delta))
			delta += 1
	for i in range(1, n):
		x = 0
		y = i
		delta = 0
		while x + delta < m and y + delta < n:
			if field[y + delta][x + delta] == 1:
				lu_to_rd[i + m - 1].append((x + delta, y + delta))
			delta += 1
	for line in lu_to_rd:
		length = len(line)
		if length <= 1:
			continue
		for i in range(length):
			for j in range(i + 1, length):
				(x1, y1) = line[i]
				(x2, y2) = line[j]
				d = abs(x1 - x2)
				ans += cs.get_diagonal_sum(x1 + d + 1, y1 - d + 1, x2 + d, y2 - d)
	field = rotate(field)[:]
print(ans)


import sys
readline = sys.stdin.readline
(H, W) = map(int, readline().split())
G = [[0] * W for _ in range(H)]
L1 = [[0] * 1000 for _ in range(W + H - 1)]
geta1 = W - 1
L2 = [[0] * 1000 for _ in range(W + H - 1)]
for i in range(H):
	S = [1 if s == '#' else 0 for s in readline().strip()]
	for j in range(W):
		G[i][j] = S[j]
		if S[j]:
			L1[i - j + geta1][i] = 1
			L2[i + j][i] = 1
for sub in range(W + H - 1):
	for i in range(630):
		L1[sub][i] += L1[sub][i - 1]
		L2[sub][i] += L2[sub][i - 1]
res = 0
for su in range(2 * max(H, W) + 1):
	for w in range(max(0, su - H + 1), min(W, su + 1)):
		h = su - w
		if not G[h][w]:
			continue
		for k in range(1, min(h + 1, W - w)):
			if not G[h - k][w + k]:
				continue
			idx1 = h + w - 2 * k
			if 0 <= idx1 < H + W - 1:
				res += L2[idx1][h - k - 1] - L2[idx1][h - 2 * k]
			idx2 = h + w + 2 * k
			if 0 <= idx2 < H + W - 1:
				res += L2[idx2][h + k - 1] - L2[idx2][h]
for mi in range(1 - W, H):
	for w in range(max(0, -mi), min(W, H - mi)):
		h = mi + w
		if not G[h][w]:
			continue
		for k in range(1, min(H - h, W - w)):
			if not G[h + k][w + k]:
				continue
			idx1 = h - w - 2 * k + geta1
			if 0 <= idx1 < H + W - 1:
				res += L1[idx1][h] - L1[idx1][h - k - 1]
			idx2 = h - w + 2 * k + geta1
			if 0 <= idx2 < H + W - 1:
				res += L1[idx2][h + 2 * k] - L1[idx2][h + k - 1]
print(res)


import itertools
import sys
(H, W) = [int(i) for i in input().split(' ')]
cross = [[0] * (H + W - 1) for _ in range(H + W - 1)]
for (i, line) in enumerate(sys.stdin):
	for (j, c) in enumerate(line.strip()):
		if c == '#':
			cross[i + j][i - j + W - 1] = 1
across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]
r = 0
for i in range(H + W - 1):
	for j in range(H + W - 1):
		if cross[i][j] != 1:
			continue
		for k in range(j + 1, H + W - 1):
			if cross[i][k] == 1:
				if i - (k - j) >= 0:
					r += across[i - (k - j)][k + 1] - across[i - (k - j)][j]
				if i + (k - j) < H + W - 1:
					r += across[i + (k - j)][k + 1] - across[i + (k - j)][j]
for i in range(H + W - 1):
	for j in range(H + W - 1):
		if cross[j][i] != 1:
			continue
		for k in range(j + 1, H + W - 1):
			if cross[k][i] == 1:
				if i - (k - j) >= 0:
					r += across2[i - (k - j)][k] - across2[i - (k - j)][j + 1]
				if i + (k - j) < H + W - 1:
					r += across2[i + (k - j)][k] - across2[i + (k - j)][j + 1]
print(r)


(H, W) = map(int, input().split())
grid = []
for i in range(H):
	grid.append(list(input()))
res = 0
cross_posi = [[0] * (H + W - 1) for _ in range(H + W - 1)]
for i in range(H):
	for j in range(W):
		if grid[i][j] == '#':
			cross_posi[i + j][i - j + W - 1] = 1
cross_posi_1 = [[0] * (H + W) for _ in range(H + W - 1)]
for i in range(H + W - 1):
	r = 0
	for j in range(H + W - 1):
		r += cross_posi[i][j]
		cross_posi_1[i][j + 1] = r
cross_posi_2 = [[0] * (H + W) for _ in range(H + W - 1)]
for i in range(H + W - 1):
	r = 0
	for j in range(H + W - 1):
		r += cross_posi[j][i]
		cross_posi_2[i][j + 1] = r
for s in range(H + W - 1):
	for t in range((s + W + 1) % 2, H + W - 2, 2):
		if cross_posi[s][t] == 1:
			for u in range(t + 2, H + W - 1, 2):
				if cross_posi[s][u] == 1:
					d = u - t
					if s >= d:
						res += cross_posi_1[s - d][u + 1] - cross_posi_1[s - d][t]
					if s + d < H + W - 1:
						res += cross_posi_1[s + d][u + 1] - cross_posi_1[s + d][t]
for s in range(H + W - 1):
	for t in range((s + W + 1) % 2, H + W - 2, 2):
		if cross_posi[t][s] == 1:
			for u in range(t + 2, H + W - 1, 2):
				if cross_posi[u][s] == 1:
					d = u - t
					if s >= d:
						res += cross_posi_2[s - d][u] - cross_posi_2[s - d][t + 1]
					if s + d < H + W - 1:
						res += cross_posi_2[s + d][u] - cross_posi_2[s + d][t + 1]
print(res)


from itertools import product
from itertools import combinations
(h, w) = map(int, input().split())
slili = [list(input()) for i in range(h)]
coinsetli = [set() for i in range(h + w)]
for (i, j) in product(range(h), range(w)):
	if slili[i][j] == '#':
		coinsetli[i + j + 1].add(j - i)
jmin = -304
jmin2 = jmin + 2
coinacumdictli = [[] for i in range(h + w)]
for i in range(1, h + w):
	tmp = 0
	tt = i % 2 - 1
	for j in range(jmin + tt, 303, 2):
		if j in coinsetli[i]:
			tmp += 1
		coinacumdictli[i].append(tmp)
coinacumdictli2 = [[] for i in range(h + w)]
for i in range(1, h + w):
	tt = i % 2 - 1
	for j in range(len(coinacumdictli[i]) - 1):
		coinacumdictli2[i].append(coinacumdictli[i][j] + coinacumdictli[i][j + 1])
coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
	tt = i % 2 - 1

	def rescale(x):
		return (x - jmin2 - tt) // 2
	coinlili[i] = sorted(list(map(rescale, coinsetli[i])))
ansdouble = 0
for i in range(1, h + w):
	tt = i % 2 - 1
	for (x, y) in combinations(coinlili[i], 2):
		j = 2 * (y - x)
		imj = i - j
		ipj = i + j
		if imj >= 1:
			ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
		if ipj <= h + w - 1:
			ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]
for i in range(h):
	slili[i].reverse()
coinsetli = [set() for i in range(h + w)]
for (i, j) in product(range(h), range(w)):
	if slili[i][j] == '#':
		coinsetli[i + j + 1].add(j - i)
jmin = -304
jmin2 = jmin + 2
coinacumdictli = [[] for i in range(h + w)]
for i in range(1, h + w):
	tmp = 0
	tt = i % 2 - 1
	for j in range(jmin + tt, 303, 2):
		if j in coinsetli[i]:
			tmp += 1
		coinacumdictli[i].append(tmp)
coinacumdictli2 = [[] for i in range(h + w)]
for i in range(1, h + w):
	tt = i % 2 - 1
	for j in range(len(coinacumdictli[i]) - 1):
		coinacumdictli2[i].append(coinacumdictli[i][j] + coinacumdictli[i][j + 1])
coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
	tt = i % 2 - 1

	def rescale(x):
		return (x - jmin2 - tt) // 2
	coinlili[i] = sorted(list(map(rescale, coinsetli[i])))
for i in range(1, h + w):
	tt = i % 2 - 1
	for (x, y) in combinations(coinlili[i], 2):
		j = 2 * (y - x)
		imj = i - j
		ipj = i + j
		if imj >= 1:
			ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
		if ipj <= h + w - 1:
			ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]
print(ansdouble // 2)


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
(H, W) = reads()
S = []
for _ in range(H):
	S.append(input())
N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
	for j in range(W):
		field[i + j][i - j + W] = int(S[i][j] == '#')
accRow = [None] * N
for i in range(N):
	accRow[i] = [0] + list(accumulate((field[i][j] for j in range(N))))
accCol = [None] * N
for i in range(N):
	accCol[i] = [0] + list(accumulate((field[j][i] for j in range(N))))
ans = 0
for i in range(N):
	for j in range((i + W) % 2, N, 2):
		for k in range(j + 2, N, 2):
			d = k - j
			if field[i][j] == field[i][k] == 1:
				if i - d >= 0:
					ans += accRow[i - d][k + 1] - accRow[i - d][j]
				if i + d < N:
					ans += accRow[i + d][k + 1] - accRow[i + d][j]
			if field[j][i] == field[k][i] == 1:
				if i - d >= 0:
					ans += accCol[i - d][k] - accCol[i - d][j + 1]
				if i + d < N:
					ans += accCol[i + d][k] - accCol[i + d][j + 1]
print(ans)