CSES 3417 ↗

Border Subgrid Count I

For each letter, the number of square subgrids whose border is entirely that letter.

0
submissions
—
best score

You are given a grid of letters. Your task is to calculate, for each letter, the number of square subgrids whose border consists of that letter.

Input

The first line has two integers n and k: the size of the grid and the number of letters. The letters are the first k uppercase letters.

After this, there are n lines that describe the grid. Each line has n letters.

Output

Print k lines: for each letter, the number of subgrids.

Constraints

  • 1≤n≤3000
  • 1≤k≤26

Example

Input:

5 3
ABBBC
ABABC
ABBBC
ABBBC
CCCCC

Output:

5
14
9

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BorderSubgridCountI/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.