The answer array has to have N elements and K distinct elements.

Thus, choose K distinct elements to be from 1 to K and remaining N - K elements to be 1.

The sum of which is : (K * (K + 1) / 2) + N - K

Let P[i] be the difference between the number of days Bob studied and the number of days he didn't till ith day.

Thus, we have to ensure that P[i] >  = 0 for 1 <  = i <  = N.

Iterate over all i and greedily flip 0 to 1 whenever P[i] becomes negative.

Let us consider an array of N elements b, consisting of 0 and 1, 0 denotes Snorlax doesn't work out on the ith day and 1 indicates that he does.

The window size is K.

Let us look at the ith window, when you slide one window further, from the subarray sum, we have to subtract b[i] and add b[i + k]. Effectively adding b[i + k] - b[i]. If this value is 1, we can surely say that b[i] is 0 and b[i + k] is 1 and if this value  - 1, the reverse is true.

If this difference is 0, we can say that b[i] and b[i + k] are equal but can't tell the exact values.

If the absolute value of this difference is more than 1, array construction is impossible.

Note that, we thus get relations between b[i], b[i + k], b[i + 2k]... and so on. We just check if these relations are consistent. If we just know any of this group, we can figure out the rest of this group. Note that part of a group are those indices who have same remainder on division with l.

At an index, we cannot get more than 1 invalid value. Meaning, we can't say that b[i] is neither 0 nor 1.

There is still one constraint we haven't enforced yet and this is the sum of the values in 1st window, till now, we only looked the difference between consecutive windows.

We enforce this constraint by making 1 those values that are unknown and occur at the end of the 1st window (the end because we have to minimise the number of 1's too and the ending values have the largest remainders, it can easily be seen that those with large remainder occur fewer times than those with smaller remainder).

If we are unable to enforce the above constraint, then also making the array is impossible.

The complexity is O(N).

Let us first represent each cell with a number by 2^d[i][j]. For a grid to be palindrome, the xor of all values should have at max 1 set bit in it. For a grid to be divisible by 6, the sum of digits should be divisible by 3 and the grid should contain at least 2 even digits.

A corner case is when the grid consists of only a single element. [6] is the only single element grid possible.

Since, N * M <  = 100000, min(N, M) <  = 320 Lets suppose N <  = M, otherwise we can flip the grid diagonally and answer wont change. Lets iterate over 2 rows i and j. Let us store prefix_sums, prefix_xors and prefix_even_nos for the columns considering all rows from i to j. Let us iterate over the rightmost column k.

Now, all l's such that

• 

• 

• (pre_even[k] - pre_even[l - 1]) >  = 2

are valid leftmost columns of the grid.

For the third condition we can use 2 pointers. For first and second conditions, we can store frequency of xors along with in a [1«10][3] array and run an extra 9 size loop for second condition.

So, overall complexity will be O(min(N, M) * N * M * 10). Refer to the code for better understanding.

#include <bits/stdc++.h>

#define int         long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
int n,m;
int ans;
vector<string> s;
vector<vi> colsum,colxor,coleven;
int prexor[1<<10][3],curxor[100005],cursum[100005],cureven[100005];
void solve(){
	cin>>n>>m;
	s.resize(n+1);
	rep(i,1,n+1){
		cin>>s[i];
		s[i]='#'+s[i];
	}
	if(n>m){
		rep(i,1,n+1) s[i].resize(n+1);
		rep(i,1,n+1){
			rep(j,i,n+1){
				swap(s[i][j],s[j][i]);
			}
		}
		swap(n,m);
	}
	colsum.resize(m+1);
	colxor.resize(m+1);
	coleven.resize(m+1);
	rep(i,1,m+1){
		colsum[i].resize(n+1);
		colxor[i].resize(n+1);
		coleven[i].resize(n+1);
		rep(j,1,n+1){
			colsum[i][j]=(colsum[i][j-1]+s[j][i]-'0')%3;
			colxor[i][j]=(colxor[i][j-1]^(1<<(s[j][i]-'0')));
			coleven[i][j]=coleven[i][j-1]+((s[j][i]-'0')%2==0);
		}
	}
	rep(i,1,n+1){
		rep(j,i,n+1){
			for(int k=0;k<(1<<10);k+=2) prexor[k][0]=prexor[k][1]=prexor[k][2]=0;
			rep(k,1,m+1) curxor[k]=curxor[k-1]^colxor[k][j]^colxor[k][i-1];
			rep(k,1,m+1) cursum[k]=(cursum[k-1]+colsum[k][j]-colsum[k][i-1]+3)%3;
			rep(k,1,m+1) cureven[k]=cureven[k-1]+coleven[k][j]-coleven[k][i-1];
			int lo=0;
			rep(k,1,m+1){
				while(lo<k and cureven[k]-cureven[lo]>=2){
					prexor[curxor[lo]][cursum[lo]]++;
					lo++;
				}
				ans+=prexor[curxor[k]][cursum[k]];
				rep(l,1,10) ans+=prexor[curxor[k]^(1<<l)][cursum[k]];
			}
		}
	}
	rep(i,1,n+1){
		rep(j,1,m+1){
			if(s[i][j]=='6'){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    // cin>>t;
	while(t--){
		solve();
	}
	return 0;
}