stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

struct edge { int to, id; };

int n, vc, a[200009], b[200009], c[200009]; long long sd, ans[200009], s[200009], dist[200009]; vector<edge> g[200009];

void dfs(int pos, int pre) {

	c[pos] = 1;

	for (edge e : g[pos]) {

		if (e.to != pre) {

			dfs(e.to, pos);

			c[pos] += c[e.to];

			// e.to -> pos, increased nodes = c[e.to], decreased nodes = n - c[e.to]

			if (n - c[e.to] * 2 != 0) {

				ans[e.id] = (s[e.to] - s[pos]) / (n - c[e.to] * 2);

			}

		}

	}

}

void dfs2(int pos, int pre, int flag) {

	if (flag) vc++; sd += dist[pos];

	for (edge e : g[pos]) {

		if (e.to != pre) {

			dist[e.to] = dist[pos];

			if (ans[e.id] != -1) dist[e.to] += ans[e.id];

			dfs2(e.to, pos, (flag | (ans[e.id] == -1 ? 1 : 0)));

		}

	}

}

int main() {

	cin >> n;

	for (int i = 0; i < n - 1; i++) {

		cin >> a[i] >> b[i]; a[i]--, b[i]--;

		g[a[i]].push_back(edge{ b[i], i });

		g[b[i]].push_back(edge{ a[i], i });

	}

	for (int i = 0; i < n; i++) cin >> s[i];

	fill(ans, ans + n - 1, -1);

	dfs(0, -1);

	int zp = -1;

	for (int i = 0; i < n - 1; i++) {

		if (ans[i] == -1) zp = i;

	}

	if (zp != -1) {

		dfs2(0, -1, 0);

		ans[zp] = (s[0] - sd) / vc;

	}

	for (int i = 0; i < n - 1; i++) cout << ans[i] << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.389495451440266x):
#include <vector>

#include <iostream>

using namespace std;

struct edge {

	int to, id;

	edge() : to(-1), id(-1) {};

	edge(int to_, int id_) : to(to_), id(id_) {};

};

int n, eid = -1; vector<int> a, b, c; vector<long long> s, t; vector<vector<edge> > g;

void dfs(int pos, int pre) {

	c[pos] = 1;

	for (edge e : g[pos]) {

		if (e.to != pre) {

			dfs(e.to, pos);

			c[pos] += c[e.to];

			if (c[e.to] * 2 != n) {

				t[e.id] = (s[e.to] - s[pos]) / (n - 2 * c[e.to]);

			}

			else eid = e.id;

		}

	}

}

long long calc(int pos, int pre, long long cumdist) {

	long long ret = cumdist;

	for (edge e : g[pos]) {

		if (e.to != pre) {

			ret += calc(e.to, pos, cumdist + t[e.id]);

		}

	}

	return ret;

}

int main() {

	cin.tie(0);

	cin >> n;

	a = vector<int>(n - 1);

	b = vector<int>(n - 1);

	s = vector<long long>(n);

	g = vector<vector<edge> >(n);

	for (int i = 0; i < n - 1; ++i) {

		cin >> a[i] >> b[i]; --a[i], --b[i];

		g[a[i]].push_back(edge(b[i], i));

		g[b[i]].push_back(edge(a[i], i));

	}

	for (int i = 0; i < n; ++i) {

		cin >> s[i];

	}

	c = vector<int>(n);

	t = vector<long long>(n - 1);

	dfs(0, -1);

	if (eid != -1) {

		long long cur = calc(a[eid], -1, 0);

		t[eid] = (s[a[eid]] - cur) / (n / 2);

	}

	for (int i = 0; i < n - 1; ++i) {

		cout << t[i] << '\n';

	}

	return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e16;



/*

<url:https://abc087.contest.atcoder.jp/tasks/abc087_b>

問題文============================================================

 あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。

 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

 

 同じ種類の硬貨どうしは区別できません。

 2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

=================================================================



解説=============================================================

全探索

================================================================

*/

int main(void) {

	cin.tie(0); ios::sync_with_stdio(false);

    ll A,B,C,X; cin >> A >> B >> C >> X;

    

 //   ll cntA = X/A, cntB = X/B, cntC = X/C;

    

    ll ans = 0;

    for(int i = 0; i <= A;i++){

        for(int j = 0; j <= B; j++){

            for(int k = 0; k  <= C;k++){

                if(500*i + 100*j + 50*k == X){

                    ans++;

                }

            }

        }

    }

    

    cout << ans << endl;

    

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.6268961258953802x):
#include<cstdio>

using namespace std;

int A, B, C;

int X;

int solve(){

int result = 0;

for(int i = 0; i <= A; ++i){

for(int j = 0; j <= B; ++j){

for(int k = 0; k <= C; ++k){

int tmp = i * 500 + j * 100 + k * 50;

if(tmp == X) result++;

}

}

}

return result;

}

int main(){

scanf("%d%d%d%d", &A, &B, &C, &X);

int result = solve();

printf("%d\n", result);

return 0;

}
// Slower C++ solution:
#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#include <math.h>

#include <time.h>

#include <vector>

#include <map>

#include <set>

using namespace std;



int main()

{

	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	int x,a,b,c;

	cin>>a>>b>>c>>x;

	int tot=0;

	for(int i=0;i<=a;i++)

	{

		for(int j=0;j<=b;j++)

		

		{

			for(int k=0;k<=c;k++)

			{

				if(500*i+100*j+50*k==x)

				{

					tot++;

				}

			}

		}

	}

	cout<<tot;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5506759768355343x):
#include<cstdio>

using namespace std;

int A, B, C;

int X;

int solve(){

int result = 0;

for(int i = 0; i <= A; ++i){

for(int j = 0; j <= B; ++j){

for(int k = 0; k <= C; ++k){

int tmp = i * 500 + j * 100 + k * 50;

if(tmp == X) result++;

}

}

}

return result;

}

int main(){

scanf("%d%d%d%d", &A, &B, &C, &X);

int result = solve();

printf("%d\n", result);

return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iomanip>

using namespace std;

int a,b,c,x,d;



int main()

{

    cin>>a>>b>>c>>x;

    for(int i = 0;i <= a;i ++)

    {

        for(int j = 0;j <= b;j ++)

        {

            for(int k = 0;k <= c;k ++)

                if(i * 500 + j * 100 + k * 50 == x)d ++;

        }

    }

    cout<<d<<endl;

}


// Faster C++ solution for the same problem (measured speedup: 3.586493042222358x):
#include<cstdio>

using namespace std;

int A, B, C;

int X;

int solve(){

int result = 0;

for(int i = 0; i <= A; ++i){

for(int j = 0; j <= B; ++j){

for(int k = 0; k <= C; ++k){

int tmp = i * 500 + j * 100 + k * 50;

if(tmp == X) result++;

}

}

}

return result;

}

int main(){

scanf("%d%d%d%d", &A, &B, &C, &X);

int result = solve();

printf("%d\n", result);

return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

int main(){

       int a,b,c,x;

       scanf("%d%d%d%d",&a,&b,&c,&x);

       int n=0;

       for(int i=0;i<=a;i++){

              for(int j=0;j<=b;j++){

                     for(int k=0;k<=c;k++){

                            if(i*500+j*100+k*50==x){

                                   n++;

                            }

                     }

              }

       }

       printf("%d",n);

       return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.4744749207990506x):
#include<cstdio>

using namespace std;

int A, B, C;

int X;

int solve(){

int result = 0;

for(int i = 0; i <= A; ++i){

for(int j = 0; j <= B; ++j){

for(int k = 0; k <= C; ++k){

int tmp = i * 500 + j * 100 + k * 50;

if(tmp == X) result++;

}

}

}

return result;

}

int main(){

scanf("%d%d%d%d", &A, &B, &C, &X);

int result = solve();

printf("%d\n", result);

return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

using namespace std;

int main(){

    int a,b,c;

    int x;

    scanf("%d%d%d%d",&a,&b,&c,&x);

    int i,j,k;

    int cnt = 0;

    for(i = 0; i <= a; i++){

        for(j = 0; j <= b; j++){

            for(k = 0; k <= c; k++){

                if(i*500+j*100+k*50==x)

                    cnt++;

            }

        }

    }

    printf("%d\n",cnt);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.476589005170185x):
#include<cstdio>

using namespace std;

int A, B, C;

int X;

int solve(){

int result = 0;

for(int i = 0; i <= A; ++i){

for(int j = 0; j <= B; ++j){

for(int k = 0; k <= C; ++k){

int tmp = i * 500 + j * 100 + k * 50;

if(tmp == X) result++;

}

}

}

return result;

}

int main(){

scanf("%d%d%d%d", &A, &B, &C, &X);

int result = solve();

printf("%d\n", result);

return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



//#define _FILES

#define PB push_back

#define MP make_pair

#define X first

#define Y second

const int MAXN = 2005;



int f[MAXN][MAXN], h[MAXN][MAXN], v[MAXN][MAXN], c[MAXN][MAXN];



int main()

{

    ios_base::sync_with_stdio(false);



    #ifdef _FILES

        freopen("","r",stdin);

        freopen("","w",stdout);

    #endif // _FILES

    int n, m, q;

    cin >> n >> m >> q;

    for (int i=1;i<=n;i++)

    {

        string s;

        cin >> s;

        for (int j=0;j<m;j++)

        {

            if (s[j] == '1')

            {

                f[i][j+1] = 1;

            }

        }

    }



    for (int i=n;i>=1;i--)

    {

        for (int j=m;j>=1;j--)

        {

            c[i][j] = c[i+1][j] + c[i][j+1] - c[i+1][j+1];



            if (f[i][j])

            {

                c[i][j]++;

                if (f[i+1][j])

                {

                    c[i][j]--;

                }



                if (f[i][j+1])

                {

                    c[i][j]--;

                }

            }



            v[i][j] = v[i+1][j];

            if ((f[i][j]) && (f[i][j+1]))

            {

                v[i][j]++;

            }



            h[i][j] = h[i][j+1];

            if ((f[i][j]) && (f[i+1][j]))

            {

                h[i][j]++;

            }

        }

    }



    for (int i=0;i<q;i++)

    {

        int x1, y1, x2, y2;

        cin >> x1 >> y1 >> x2 >> y2;

        int ans = c[x1][y1] + h[x2][y1] - h[x2][y2+1] + v[x1][y2] - v[x2+1][y2] - c[x2+1][y1] - c[x1][y2+1] + c[x2+1][y2+1];

        cout << ans << "\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.208558120065382x):
#include <cstdio>

int f_1[2005][2005],f_2[2005][2005],a[2005][2005],sum[2005][2005];

char mp[2005];

int main(){

	int n,m,q;

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++){

		scanf("%s",mp+1);

		for(int j=1;j<=m;j++){

			a[i][j]=mp[j]-'0';

			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

			f_1[i][j]=f_1[i-1][j]+f_1[i][j-1]-f_1[i-1][j-1];

			f_2[i][j]=f_2[i-1][j]+f_2[i][j-1]-f_2[i-1][j-1];

			if(a[i][j]==1){

				if(a[i-1][j]==1){

					f_1[i][j]++;

				}

				if(a[i][j-1]==1){

					f_2[i][j]++;

				}

			}

		}

	}

	int x1,y1,x2,y2;

	int ans;

	while(q--){

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

		ans-=f_1[x2][y2]-f_1[x1][y2]-f_1[x2][y1-1]+f_1[x1][y1-1];

		ans-=f_2[x2][y2]-f_2[x1-1][y2]-f_2[x2][y1]+f_2[x1-1][y1];

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)



int N,M,Q;

char str[2005];

int fk[2005][2005],f2[2005][2005],f3[2005][2005];



int main(){

	scanf("%d%d%d",&N,&M,&Q);

	F(i,1,N){

		scanf("%s",str+1);

		F(j,1,M){

			if(str[j]=='1'){

				fk[i][j]=1;

				if(fk[i-1][j]) f2[i-1][j]=1;

				if(fk[i][j-1]) f3[i][j-1]=1;

			}

		}

	}

	F(i,1,N) F(j,1,M)

		fk[i][j]+=fk[i-1][j]+fk[i][j-1]-fk[i-1][j-1],

		f2[i][j]+=f2[i-1][j]+f2[i][j-1]-f2[i-1][j-1],

		f3[i][j]+=f3[i-1][j]+f3[i][j-1]-f3[i-1][j-1];

	F(i,1,Q){

		int X1,Y1,X2,Y2;

		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);

		int Dots=fk[X2][Y2]-fk[X1-1][Y2]-fk[X2][Y1-1]+fk[X1-1][Y1-1];

		int Edges=f2[X2-1][Y2]-f2[X1-1][Y2]-f2[X2-1][Y1-1]+f2[X1-1][Y1-1]+f3[X2][Y2-1]-f3[X1-1][Y2-1]-f3[X2][Y1-1]+f3[X1-1][Y1-1];

		printf("%d\n",Dots-Edges);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.0403330780059745x):
#include <cstdio>

int f_1[2005][2005],f_2[2005][2005],a[2005][2005],sum[2005][2005];

char mp[2005];

int main(){

	int n,m,q;

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++){

		scanf("%s",mp+1);

		for(int j=1;j<=m;j++){

			a[i][j]=mp[j]-'0';

			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

			f_1[i][j]=f_1[i-1][j]+f_1[i][j-1]-f_1[i-1][j-1];

			f_2[i][j]=f_2[i-1][j]+f_2[i][j-1]-f_2[i-1][j-1];

			if(a[i][j]==1){

				if(a[i-1][j]==1){

					f_1[i][j]++;

				}

				if(a[i][j-1]==1){

					f_2[i][j]++;

				}

			}

		}

	}

	int x1,y1,x2,y2;

	int ans;

	while(q--){

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

		ans-=f_1[x2][y2]-f_1[x1][y2]-f_1[x2][y1-1]+f_1[x1][y1-1];

		ans-=f_2[x2][y2]-f_2[x1-1][y2]-f_2[x2][y1]+f_2[x1-1][y1];

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MN 2005

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

int n,m,q;

bool mp[MN][MN];

int l[MN][MN],h[MN][MN],b[MN][MN];

int main(){

	n=read(),m=read(),q=read();char c[MN];

	for(int i=1;i<=n;i++){

		scanf("%s",c+1);

		for(int j=1;j<=m;j++) mp[i][j]=c[j]=='1';

	}

	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){

		l[i][j]=l[i-1][j]+l[i][j-1]-l[i-1][j-1]+(mp[i][j]&&mp[i][j-1]);

		h[i][j]=h[i-1][j]+h[i][j-1]-h[i-1][j-1]+(mp[i][j]&&mp[i-1][j]);

		b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(mp[i][j]);

	}

	int ans,x1,y1,x2,y2;

	while(q--){

		x1=read(),y1=read(),x2=read(),y2=read();

		ans=0;

		ans+=b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];

		ans-=l[x2][y2]-l[x2][y1]-l[x1-1][y2]+l[x1-1][y1];

		ans-=h[x2][y2]-h[x2][y1-1]-h[x1][y2]+h[x1][y1-1];

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.0283475256556x):
#include <cstdio>

int f_1[2005][2005],f_2[2005][2005],a[2005][2005],sum[2005][2005];

char mp[2005];

int main(){

	int n,m,q;

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++){

		scanf("%s",mp+1);

		for(int j=1;j<=m;j++){

			a[i][j]=mp[j]-'0';

			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

			f_1[i][j]=f_1[i-1][j]+f_1[i][j-1]-f_1[i-1][j-1];

			f_2[i][j]=f_2[i-1][j]+f_2[i][j-1]-f_2[i-1][j-1];

			if(a[i][j]==1){

				if(a[i-1][j]==1){

					f_1[i][j]++;

				}

				if(a[i][j-1]==1){

					f_2[i][j]++;

				}

			}

		}

	}

	int x1,y1,x2,y2;

	int ans;

	while(q--){

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

		ans-=f_1[x2][y2]-f_1[x1][y2]-f_1[x2][y1-1]+f_1[x1][y1-1];

		ans-=f_2[x2][y2]-f_2[x1-1][y2]-f_2[x2][y1]+f_2[x1-1][y1];

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



//#define _FILES

#define PB push_back

#define MP make_pair

#define X first

#define Y second

const int MAXN = 2005;



int f[MAXN][MAXN], h[MAXN][MAXN], v[MAXN][MAXN], c[MAXN][MAXN];



int main()

{

    ios_base::sync_with_stdio(false);



    #ifdef _FILES

        freopen("","r",stdin);

        freopen("","w",stdout);

    #endif // _FILES

    int n, m, q;

    cin >> n >> m >> q;

    for (int i=1;i<=n;i++)

    {

        string s;

        cin >> s;

        for (int j=0;j<m;j++)

        {

            if (s[j] == '1')

            {

                f[i][j+1] = 1;

            }

        }

    }



    for (int i=n;i>=1;i--)

    {

        for (int j=m;j>=1;j--)

        {

            c[i][j] = c[i+1][j] + c[i][j+1] - c[i+1][j+1];



            if (f[i][j])

            {

                c[i][j]++;

                if (f[i+1][j])

                {

                    c[i][j]--;

                }



                if (f[i][j+1])

                {

                    c[i][j]--;

                }

            }



            v[i][j] = v[i+1][j];

            if ((f[i][j]) && (f[i][j+1]))

            {

                v[i][j]++;

            }



            h[i][j] = h[i][j+1];

            if ((f[i][j]) && (f[i+1][j]))

            {

                h[i][j]++;

            }

        }

    }



    for (int i=0;i<q;i++)

    {

        int x1, y1, x2, y2;

        cin >> x1 >> y1 >> x2 >> y2;

        int ans = c[x1][y1] + h[x2][y1] - h[x2][y2+1] + v[x1][y2] - v[x2+1][y2] - c[x2+1][y1] - c[x1][y2+1] + c[x2+1][y2+1];

        cout << ans << "\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.212236582135811x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 2010

int sum1[MAXN][MAXN],sum2[MAXN][MAXN],cl[MAXN][MAXN],n,m,q;

char s[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)

	{

		scanf("%s",s[i]+1);

		s[i][0]='0';

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]=sum1[i][j-1];

			sum2[i][j]=sum2[i][j-1];

			if(s[i][j]=='1'&&s[i-1][j]=='1')

				sum1[i][j]++;

			if(s[i][j]=='1'&&s[i][j-1]=='0')

				sum2[i][j]++;

			if(s[i][j]=='1'&&s[i][j+1]=='1')

				cl[i][j]=1;

			cl[i][j]+=cl[i-1][j];

		}

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]+=sum1[i-1][j];

			sum2[i][j]+=sum2[i-1][j];

		}

	}

	int x1,y1,x2,y2;

	while(q--)

	{

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		x1--,y1--;

		int ans=sum2[x2][y2]-sum2[x1][y2]-sum2[x2][y1]+sum2[x1][y1]+cl[x2][y1]-cl[x1][y1];

		ans-=sum1[x2][y2]-sum1[x1+1][y2]-sum1[x2][y1]+sum1[x1+1][y1];

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)



int N,M,Q;

char str[2005];

int fk[2005][2005],f2[2005][2005],f3[2005][2005];



int main(){

	scanf("%d%d%d",&N,&M,&Q);

	F(i,1,N){

		scanf("%s",str+1);

		F(j,1,M){

			if(str[j]=='1'){

				fk[i][j]=1;

				if(fk[i-1][j]) f2[i-1][j]=1;

				if(fk[i][j-1]) f3[i][j-1]=1;

			}

		}

	}

	F(i,1,N) F(j,1,M)

		fk[i][j]+=fk[i-1][j]+fk[i][j-1]-fk[i-1][j-1],

		f2[i][j]+=f2[i-1][j]+f2[i][j-1]-f2[i-1][j-1],

		f3[i][j]+=f3[i-1][j]+f3[i][j-1]-f3[i-1][j-1];

	F(i,1,Q){

		int X1,Y1,X2,Y2;

		scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);

		int Dots=fk[X2][Y2]-fk[X1-1][Y2]-fk[X2][Y1-1]+fk[X1-1][Y1-1];

		int Edges=f2[X2-1][Y2]-f2[X1-1][Y2]-f2[X2-1][Y1-1]+f2[X1-1][Y1-1]+f3[X2][Y2-1]-f3[X1-1][Y2-1]-f3[X2][Y1-1]+f3[X1-1][Y1-1];

		printf("%d\n",Dots-Edges);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.04389273379216x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 2010

int sum1[MAXN][MAXN],sum2[MAXN][MAXN],cl[MAXN][MAXN],n,m,q;

char s[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)

	{

		scanf("%s",s[i]+1);

		s[i][0]='0';

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]=sum1[i][j-1];

			sum2[i][j]=sum2[i][j-1];

			if(s[i][j]=='1'&&s[i-1][j]=='1')

				sum1[i][j]++;

			if(s[i][j]=='1'&&s[i][j-1]=='0')

				sum2[i][j]++;

			if(s[i][j]=='1'&&s[i][j+1]=='1')

				cl[i][j]=1;

			cl[i][j]+=cl[i-1][j];

		}

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]+=sum1[i-1][j];

			sum2[i][j]+=sum2[i-1][j];

		}

	}

	int x1,y1,x2,y2;

	while(q--)

	{

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		x1--,y1--;

		int ans=sum2[x2][y2]-sum2[x1][y2]-sum2[x2][y1]+sum2[x1][y1]+cl[x2][y1]-cl[x1][y1];

		ans-=sum1[x2][y2]-sum1[x1+1][y2]-sum1[x2][y1]+sum1[x1+1][y1];

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define MN 2005

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

int n,m,q;

bool mp[MN][MN];

int l[MN][MN],h[MN][MN],b[MN][MN];

int main(){

	n=read(),m=read(),q=read();char c[MN];

	for(int i=1;i<=n;i++){

		scanf("%s",c+1);

		for(int j=1;j<=m;j++) mp[i][j]=c[j]=='1';

	}

	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){

		l[i][j]=l[i-1][j]+l[i][j-1]-l[i-1][j-1]+(mp[i][j]&&mp[i][j-1]);

		h[i][j]=h[i-1][j]+h[i][j-1]-h[i-1][j-1]+(mp[i][j]&&mp[i-1][j]);

		b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+(mp[i][j]);

	}

	int ans,x1,y1,x2,y2;

	while(q--){

		x1=read(),y1=read(),x2=read(),y2=read();

		ans=0;

		ans+=b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];

		ans-=l[x2][y2]-l[x2][y1]-l[x1-1][y2]+l[x1-1][y1];

		ans-=h[x2][y2]-h[x2][y1-1]-h[x1][y2]+h[x1][y1-1];

		printf("%d\n",ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.031898716834365x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 2010

int sum1[MAXN][MAXN],sum2[MAXN][MAXN],cl[MAXN][MAXN],n,m,q;

char s[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)

	{

		scanf("%s",s[i]+1);

		s[i][0]='0';

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]=sum1[i][j-1];

			sum2[i][j]=sum2[i][j-1];

			if(s[i][j]=='1'&&s[i-1][j]=='1')

				sum1[i][j]++;

			if(s[i][j]=='1'&&s[i][j-1]=='0')

				sum2[i][j]++;

			if(s[i][j]=='1'&&s[i][j+1]=='1')

				cl[i][j]=1;

			cl[i][j]+=cl[i-1][j];

		}

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]+=sum1[i-1][j];

			sum2[i][j]+=sum2[i-1][j];

		}

	}

	int x1,y1,x2,y2;

	while(q--)

	{

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		x1--,y1--;

		int ans=sum2[x2][y2]-sum2[x1][y2]-sum2[x2][y1]+sum2[x1][y1]+cl[x2][y1]-cl[x1][y1];

		ans-=sum1[x2][y2]-sum1[x1+1][y2]-sum1[x2][y1]+sum1[x1+1][y1];

		printf("%d\n",ans);

	}

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



int n,m,t,ans,k,a[2010][2010],b[2010][2010],c[2010][2010];

char mp[2010][2010];



int main()

{

	scanf("%d%d%d",&n,&m,&t);

	for(int i=1; i<=n; i++)

		scanf("%s",mp[i]+1);

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=m; j++)

		{

			a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-1];

			b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1];

			c[j][i]=c[j][i-1]+c[j-1][i]-c[j-1][i-1];

			if(mp[i][j]=='1')a[i][j]++;

			if(mp[i][j-1]=='1'&&mp[i][j]=='1')b[i][j]++;

			if(mp[i-1][j]=='1'&&mp[i][j]=='1')c[j][i]++;

		}

	}

	while(t--)

	{

		int x,y,xx,yy;

		scanf("%d%d%d%d",&x,&y,&xx,&yy);

		k=a[xx][yy]-a[x-1][yy]+a[x-1][y-1]-a[xx][y-1];

		ans=b[xx][yy]-b[xx][y]-b[x-1][yy]+b[x-1][y];

		ans+=c[yy][xx]-c[yy][x]-c[y-1][xx]+c[y-1][x];

		printf("%d\n",k-ans);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.043650637667486x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 2010

int sum1[MAXN][MAXN],sum2[MAXN][MAXN],cl[MAXN][MAXN],n,m,q;

char s[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i=1;i<=n;i++)

	{

		scanf("%s",s[i]+1);

		s[i][0]='0';

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]=sum1[i][j-1];

			sum2[i][j]=sum2[i][j-1];

			if(s[i][j]=='1'&&s[i-1][j]=='1')

				sum1[i][j]++;

			if(s[i][j]=='1'&&s[i][j-1]=='0')

				sum2[i][j]++;

			if(s[i][j]=='1'&&s[i][j+1]=='1')

				cl[i][j]=1;

			cl[i][j]+=cl[i-1][j];

		}

		for(int j=1;j<=m;j++)

		{

			sum1[i][j]+=sum1[i-1][j];

			sum2[i][j]+=sum2[i-1][j];

		}

	}

	int x1,y1,x2,y2;

	while(q--)

	{

		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

		x1--,y1--;

		int ans=sum2[x2][y2]-sum2[x1][y2]-sum2[x2][y1]+sum2[x1][y1]+cl[x2][y1]-cl[x1][y1];

		ans-=sum1[x2][y2]-sum1[x1+1][y2]-sum1[x2][y1]+sum1[x1+1][y1];

		printf("%d\n",ans);

	}

}