{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eInnokenty works at a flea market and sells some \u003cspan class\u003d\"tex-font-style-striked\"\u003erandom stuff\u003c/span\u003e rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in $$$n \\cdot m$$$ colored pieces that form a rectangle with $$$n$$$ rows and $$$m$$$ columns. \u003c/p\u003e\u003cp\u003eThe colored pieces attracted Innokenty\u0027s attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of \u003cspan class\u003d\"tex-font-style-bf\"\u003eequal\u003c/span\u003e heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.\u003c/p\u003e\u003cp\u003eInnokenty has not yet decided what part he will cut out, but he is sure that the flag\u0027s boundaries should go along grid lines. Also, Innokenty won\u0027t rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/c25064d638f35eff62fe918c9a1dd70b?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/161dce0eeb653e3e37017cb48289e048?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/77eb5267b01dc92a0f58bb5e9905d914?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eThese subrectangles are flags.\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/313c676474b284b96e0a0df4b1fe24bc?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ad31d853a706409f27c6b84ac8db0057?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/879ff38c577c495b9eaba3eda333d41f?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/5a5f4ea8dbc83b70c989e5325ada546f?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/7ddacc8ea7ceffceae6b832894e4d2e4?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/24eced7512a8a11c8ff337b09ca7a36a?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eThese subrectangles are not flags.\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\le n, m \\le 1\\,000$$$)\u0026nbsp;— the number of rows and the number of columns on the blanket.\u003c/p\u003e\u003cp\u003eEach of the next $$$n$$$ lines contains $$$m$$$ lowercase English letters from \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\u0027 to \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003ez\u003c/span\u003e\u0027 and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIn the only line print the number of subrectangles which form valid flags.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 3\naaa\nbbb\nccb\nddd\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6 1\na\na\nb\nb\nc\nc\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/14126c3cc9648e16564ad8b66efc852f?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/1886abaa02e3073611f34e565c8a4b10?v\u003d1714729595\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-size-small\"\u003eThe selected subrectangles are flags in the first example.\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e"}}]}