akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    long long int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    long long int diff = b - a;
    long long int low = 0, high = n - 1;
    while (low < high) {
        long long int mid = (low + high) / 2;
        long long int n1 = (c + d) * mid - n * d + d;
        long long int n2 = (c + d) * mid - n * c + c;
        if (n1 <= diff && diff <= n2) {
            cout << "YES" << endl;
            return 0;
        }
        if (n1 > diff) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    if ((c + d) * low - n * d + d <= diff && (c + d) * low - n * c + c >= diff) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>

using namespace std;

#define td typedef
td long long ll;

ll in()
{
    ll a;
    scanf("%lld",&a);
    return a;
}

bool prime[100005];
int chumu[100005];

int main()
{
    prime[0]=prime[1]=1;
    for(ll i=2;i<=100003;i++)
    {
        if(!prime[i])
        {
            for(ll j=i*i;j<=100003;j+=i)
                prime[j]=1;
        }
    }
    for(int i=1;i<=100003;i++)
    {
        if((!prime[i])&&(!prime[(i+1)/2]))
            chumu[i]=chumu[i-1]+1;
        else
            chumu[i]=chumu[i-1];
    }
    int t=in();
    while(t--)
    {
        int x=in(),y=in();
        printf("%d\n",chumu[y]-chumu[x-1]);
    }
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N , l , r , sum;
    cin >> N;
    sum = 0;
        
    for(int i = 0; i < N; i++){
        cin >> l >> r;
        sum += (r - l + 1);
    }
    cout << sum << endl;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl "\n"
#define ll long long 

int main() {
    IOS;
    double n, x, t;
    cin >> n >> x >> t;
    cout << (int)(ceil(n / x) * t);
    return 0;
}

Measured memory_bytes: 3716
#include <stdio.h>
#include <stdlib.h>
int line1[2000010];
int c(const void *v1,const void *v2){
    return *(int *)v1-*(int *)v2;
}

int bs(int r,int l,int k){
    int m;
    while(l-r > 1){
        m=(r+l)/2;
        if(line1[m]==k)
            return m;
        if(line1[m] <= k)
            r=m+1;
        else
            l=m-1;
    }
    return l;
}
int main(void){
    int line[1101],N,M,i,t,o,temp,ans,temp1;
    for(;ans=0,line[0]=0,scanf("%d %d",&N,&M),N+M;){
        for(i=1;i<=N;i++)
            scanf("%d",&line[i]);
        for(t=0,i=0;i<N+1;i++){
            for(o=0;o<N+1;o++){
                line1[t++]=line[i]+line[o];
            }
        }
        qsort(line1,t,sizeof(int),c);
        for(i=t-1;i>=0;i--){
            if(M>line1[i])
                break;
        }
        for(;i >= 0;i--){
            temp=line1[i]+line1[bs(0,t-1,M-line1[i])];
            if(ans < temp && M>=temp)
                ans=temp;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 9676
#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

#define MAX_N 100000

int N;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> s;
    
    vector<vector<char> > sw = {{'W','W'}, {'S', 'S'}, {'S', 'W'}, {'W', 'S'} };
    REP(i,4) {
        vector<char> ans = sw[i];
        FOR(j,2,N+2) {
            if (s[(j-1)%N] == 'o' && ans[j-1] == 'S') {
                ans.pb(ans[j-2] == 'S' ? 'S' : 'W');
            }
            else if (s[(j-1)%N] == 'o' && ans[j-1] == 'W') {
                ans.pb(ans[j-2] == 'S' ? 'W' : 'S');
            }
            else if (s[(j-1)%N] == 'x' && ans[j-1] == 'S') {
                ans.pb(ans[j-2] == 'S' ? 'W' : 'S');
            }
            else if (s[(j-1)%N] == 'x' && ans[j-1] == 'W') {
                ans.pb(ans[j-2] == 'S' ? 'S' : 'W');
            }
        }
        bool success = (ans[0] == ans[N] && ans[1] == ans[N+1] );
        if(success) {
            REP(k,N) {
                cout << ans[k];
            }
            cout << endl;
            return 0;
        }
    }
    
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 720
using System;
using System.Collections.Generic;

namespace ABC121_C___Energy_Drink_Collector
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
            var N = read[0];
            var M = read[1];
            var shops = new PriorityQueue<Shop>(true);

            for(int i = 0 ; i < N ; i++)
            {
                read = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
                shops.Push(new Shop(read[0],read[1]));
            }

            Shop currentShop  = currentShop = shops.Pop();
            long amount = 0;
            while(shops.Count() > 0)
            {
                if(currentShop.stock > M) break;
                M -= currentShop.stock;
                amount += currentShop.price * currentShop.stock;
                currentShop = shops.Pop();
            }
            amount += currentShop.price * M;

            Console.WriteLine(amount);
        }
    }
    class Shop : IComparable
    {
        public long price{get;set;}
        public long stock{get;set;}

        public int CompareTo(object _shop)
        {
            Shop shop = (Shop)_shop;
            if(this.price < shop.price) return -1;
            if(this.price > shop.price) return 1;
            if(this.price == shop.price) return 0;
            return 0;
        }
        public Shop(long _price,long _stock)
        {
            this.price = _price;
            this.stock = _stock;
        }
    }

    class PriorityQueue<T> where T : IComparable
{
    private List<T> nodes;
    private Boolean isAsc;

    public PriorityQueue(Boolean _isAsc)
    {
        this.nodes = new List<T>();
        this.isAsc = _isAsc;
    }

    public int Count()
    {
        return this.nodes.Count;
    }
    public T Pop()
    {
        T returnNode = this.nodes[0];
        this.nodes[0] = this.nodes[nodes.Count-1];
        this.nodes.RemoveAt(nodes.Count-1);
        int root = 0;
        while(root*2 + 1 < this.nodes.Count)
        {
            int child = root * 2 + 1;
            if(child+1<this.nodes.Count && compare(this.nodes[child+1],this.nodes[child]) > 0) child += 1;
            if(compare(this.nodes[child],this.nodes[root]) > 0)
            {
                swap(child,root);
                root = child;
            }else{
                break;
            }
        }
        return returnNode;
    }
    public void Push(T t)
    {
        this.nodes.Add(t);
        var addPosition = nodes.Count - 1;
        while(addPosition > 0)
        {
            var parent = (int)(addPosition-1)/2;
            if(compare(nodes[addPosition],nodes[parent]) > 0 )
            {
                swap(addPosition,parent);
                addPosition = parent;
            }else{
                break;
            }
     }
    }
    private int compare(T x,T y)
    {
        return this.isAsc ? y.CompareTo(x) : x.CompareTo(y);
    }
    private void swap(int x,int y)
    {
        T temp = nodes[x];
        nodes[x] = nodes[y];
        nodes[y] = temp;
    }
}
}


Measured memory_bytes: 23872
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;

#define MAX 10
char omap[MAX][MAX];
int flag[MAX][MAX], res[MAX][MAX];
int h, w, ans;

bool check(){
    int t;
//    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
//        cout<<omap[i][j];
//        if(j==w)cout<<endl;
//    }
//    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
//        cout<<flag[i][j];
//        if(j==w)cout<<endl;
//    }
    for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
        if(omap[i][j]=='#')t=1;
        else t = 0;
        if(flag[i][j]!=t)return 0;
    }
    return 1;
}

bool cgo(int x, int y){
    //cout<<"->"<<x<<"  "<<y<<"  "<<omap[x][y]<<endl;
    if(x>h||y>w||x<1||y<1||omap[x][y]!='#')return 0;
    //cout<<"ok"<<endl;
    return 1;
}

void dfs(int x, int y){
    if(omap[x][y]=='#')flag[x][y] = 1;
    //cout<<x<<" "<<y<<endl;
    if(x==h && y==w){
        if(check())ans = 1;
    }
    if(cgo(x+1, y))dfs(x+1, y);
    flag[x+1][y] = 0;
    if(cgo(x, y+1)){
            dfs(x, y+1);
    }
    flag[x][y+1] = 0;
}

int main()
{
    while(~scanf("%d%d", &h, &w))
    {
        memset(flag, 0, sizeof(flag));
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++)
                cin>>omap[i][j];
        }
//        for(int i=1;i<=h;i++)for(int j=1;j<=w;j++){
//            cout<<omap[i][j];
//            if(j==w)cout<<endl;
//        }
        ans = 0;
        dfs(1, 1);
        if(ans)printf("Possible\n");
        else printf("Impossible\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> as(n), fs(n);
    for (auto& a : as) {
        cin >> a;
    }
    for (auto& f : fs) {
        cin >> f;
    }
    sort(as.begin(), as.end(), [&](auto& i, auto& j) { return i > j; });
    sort(fs.begin(), fs.end());
    long long lo = -1, hi = as[0] * fs.back();
    // lo impossible, hi possible.
    while (hi - lo > 1) {
        long long mid = (hi + lo)/2;
        long long required = 0;
        for (int i = 0; i < n; ++i) {
            // (a-k)*f <= mid <=> a-k <= floor(mid/f) <=> k >= a - floor(mid/f)
            required += max(0LL, as[i] - (mid/fs[i]));
        }
        if (required <= k) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << hi << endl;
    return 0;
}


Measured memory_bytes: 3456
#include <iostream>
#include <sstream>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <unordered_map>
#define has(g, i) (g.find(i) != g.end())
#define ll long long
#define MAX 100000
using namespace std;
#define ll long long
#define vll vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vvi vector<vi>
#define vvll vector<vll>
#define pq priority_queue
#define x first
#define y second

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}
	if ((n - 1 ) % 2 == 0) {
		int prev = n - 1;
		while (prev >= 0) {
			cout << arr[prev] << " ";
			prev -= 2;
		}
		prev = 1;
		while (prev < n) {
			cout << arr[prev] << " ";
			prev += 2;
		}

		cout << endl;
		
	}
	else {
		int prev = n - 1;
		while (prev >= 0) {
			cout << arr[prev] << " ";
			prev -= 2;
		}
		prev = 0;
		while (prev < n) {
			cout << arr[prev] << " ";
			prev += 2;
		}

		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main(){
  cout << fixed << setprecision(5);
  int N, M, L;
  cin >> N >> M >> L;
  vector<int> P(N), T(N), V(N);
  for (int i = 0; i < N; i++){
    cin >> P[i] >> T[i] >> V[i];
  }
  vector<vector<vector<double>>> dp(N, vector<vector<double>>(M + 1, vector<double>(M + 1, 0)));
  for (int i = 0; i < N; i++){
    dp[i][0][0] = 1;
    double p = (double) P[i] / 100;
    for (int j = 0; j < M; j++){
      for (int k = 0; k <= j; k++){
        dp[i][j + 1][k] += dp[i][j][k] * (1 - p);
        dp[i][j + 1][k + 1] += dp[i][j][k] * p;
      }
    }
  }
  for (int i = 0; i < N; i++){
    double ans = 0;
    for (int j = 0; j <= M; j++){
      double t = (double) L / V[i] + j * T[i];
      double tmp = dp[i][M][j];
      for (int k = 0; k < N; k++){
        if (k != i){
          double sum = 0;
          for (int l = 0; l <= M; l++){
            if ((double) L / V[k] + l * T[k] <= t){
              sum += dp[k][M][l];
            }
          }
          tmp *= 1 - sum;
        }
      }
      ans += tmp;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 5016
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
# define ALL(x)     (x).begin(),(x).end()
# define UNIQ(c)    (c).erase(unique(ALL((c))), end((c)))
# define mp         make_pair
# define eb         emplace_back
# define FOR(i,a,b) for(int i=(a);i<(b);++i)
# define REP(i,n)   FOR(i,0,n)
# define INIT       std::ios::sync_with_stdio(false);std::cin.tie(0);


const int MOD = 100000;

LL d[101010];
LL ans = 0;
int n, m;
int main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++)cin >> d[i], d[i] += d[i - 1];
	int a;
	int pos = 0;
	for (int i = 0; i < m; i++) {
		cin >> a;
		(ans += abs(d[pos] - d[pos + a])) % MOD;
		pos += a;
	}
	cout << ans%MOD << endl;
}

Measured memory_bytes: 3860
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,n,m;
    cin>>n;
    vector<tuple<string,int,int>> v;
    for(int i=0;i<n;i++)
    {
        string t;int k;
        cin>>t>>k;
        v.push_back(make_tuple(t,-k,i));
    }
    sort(v.begin(),v.end());
    int ans[n];
    for(int i=0;i<n;i++)
    {
        ans[i]=get<2>(v[i])+1;
    }
    for(int i=0;i<n;i++)
    cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}
		selectionSort(A, N);
		sc.close();
	}

	public static void selectionSort(int[] A, int N) {
		int count = 0;
		for (int i = 0; i < N - 1; i++) {
			int minj = i;
			for (int j = i; j < N; j++) {
				if (A[j] < A[minj]) {
					minj = j;
				}
			}
			int tmp = A[i];
			A[i] = A[minj];
			A[minj] = tmp;
			if (i != minj) {
				count++;
			}
		}
		for (int i = 0; i < N; i++) {
			if (i > 0) {
				System.out.print(" ");
			}
			System.out.print(A[i]);
		}
		System.out.printf("\n");
		System.out.println(count);
	}
}



Measured memory_bytes: 26204
#include<bits/stdc++.h>
#define reg register
#define ll long long
#define inf 0x3f3f3f3f
#define iinf 0x3f3f3f3f3f3f3f3fll
using namespace std;
string s,t;
int main()
{
	cin>>s>>t;
	for(reg int i=0;i<s.length();++i)
	{
		reg char c=s[s.length()-1];
		string tmp=s;
		s.pop_back();
		s.insert(s.begin(),c);
		if(s==t)
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

int main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    Int N; cin >> N;

    for(Int ci = 0; ci*4 <= N; ++ci) {
        if ((N-ci*4)%7 == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}


Measured memory_bytes: 256
import bisect
n = int(input())
a = list(map(int, input().split()))

a.sort()
ope = []
max_num = a[-1]
min_num = a[0]
p = bisect.bisect_left(a, 0)
for i in range(1, min(p, n - 1)):
    ope.append([max_num, a[i]])
    max_num -= a[i]
for i in range(max(p, 1), n - 1):
    ope.append([min_num, a[i]])
    min_num -= a[i]
ope.append([max_num, min_num])
print(max_num - min_num)
for i in range(n - 1):
    print(" ".join(map(str, ope[i])))

Measured memory_bytes: 66876
#include <iostream>
#include <stdio.h>
using namespace std;
int n,m;
int main(){
	int total=0;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int v; cin>>v; total+=v;
	}
	if(total<=n)cout<<n-total<<endl;
	else cout<<-1<<endl;
	
} 

Measured memory_bytes: 3632
H, W = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))

ans = []
for color, num in enumerate(A, 1):
    ans += [str(color)] * num

for h in range(H):
    if h % 2 == 0:
        print(" ".join(ans[h*W: h*W+W]))
    else:
        print(" ".join(ans[h*W: h*W+W][::-1]))

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a) ? 1 : -1)
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

struct ST {
    int a, b; //価格
    ST(int _a, int _b) : a(_a), b(_b) {}
    bool operator<(const ST &an) { return a < an.a; }
};

int main() {
    cout << fixed << setprecision(10);
    int N, M;
    cin >> N >> M;
    LLI sum = 0;
    vector<LLI> a(N);
    vector<ST> v;
    REP(i, N) {
        int tmp;
        cin >> tmp;
        a[i] = tmp;
        while(0 < tmp) {
            v.push_back(ST(tmp, i));
            tmp /= 2;
        }
    }
    RSORT(v);

    vector<int> c(N);
    REP(i, M) {
        if(v.size() <= i)
            break;
        c[v[i].b]++;
    }

    LLI ans = 0;
    REP(i, N) { ans += a[i] >> c[i]; }

    cout << ans;
    return 0;
}

Measured memory_bytes: 35172
#include "bits/stdc++.h"
using namespace std;
int p, q, r;
int main()
{
	cin >> p >> q >> r;
	cout << p + q + r - max(p, max(q, r)) << endl; 
	return 0;
}
/*
1 1 1
2 

100 100 100
200 

1 5 5
6
*/ 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;

//#define int long long
using bll = boost::multiprecision::cpp_int;
using ll = long long;
//constexpr int INF = 1e9;//INT_MAX=(1<<31)-1=2147483647
constexpr ll INF = (ll)1e18;//(1LL<<63)-1=9223372036854775807
constexpr ll MOD = (ll)1e9 + 7;
constexpr double EPS = 1e-9;
constexpr int dx[4]={1,0,-1,0};
constexpr int dy[4]={0,1,0,-1};
#ifdef LOCAL_ENV
	#define debug(var) std::cout<<#var" = "<<var<<std::endl
#else
	#define debug(var)
#endif
#define p(var) std::cout<<var<<std::endl
#define PI (acos(-1))
#define rep(i, n)   for(ll i=0, i##_length=(n); i< i##_length; ++i)
#define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i)
#define all(v) (v).begin(), (v).end()
#define uniq(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
template<typename T> inline void pv(vector<T> v) { for(ll i=0, N=v.size()-1; i<=N; i++) if(i!=N) cout << v[i] << ' '; else cout << v[i] << endl; }
template<typename T> inline T power(T x, T n){ return n ? power(x*x%MOD,n/2)*(n%2?x:1)%MOD : 1; }
template<typename T> inline T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
template<typename T> inline T lcm(T a, T b) { return a / gcd(a,  b) * b; }
template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	for (int i = 0, len = v.size(); i < len; ++i){
		s << v[i]; if (i < len - 1) s << "\t";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
	for (int i = 0, len = vv.size(); i < len; ++i){
		s << vv[i] << endl;
	}
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const map<T1, T2>& m) {
	s << "{" << endl;
	for (typeof(m.begin()) itr = m.begin(); itr != m.end(); ++itr){
		s << "\t" << (*itr).first << " : " << (*itr).second << endl;
	}
	s << "}" << endl;
	return s;
}

/*-----8<-----8<-----*/

constexpr ll HW_MAX = 1000;

ll H, W, A, B;

void input() {
	scanf("%lld%lld%lld%lld", &H, &W, &A, &B);
}

void solve() {
	if(H==1){
		rep(i,W){
			if(i<A)cout<<'1';
			else cout<<'0';
		}
		cout<<endl;
		return;
	}
	if(W==1){
		rep(i,H){
			if(i<B)cout<<'1';
			else cout<<'0';
			cout<<endl;
		}
		return;
	}
	rep(i,H){
		rep(j,W){
			if(i<B){
				if(j<A)cout<<'1';
				else cout<<'0';
			}else{
				if(j<A)cout<<'0';
				else cout<<'1';
			}
		}
		cout<<endl;
	}
}

signed main() {
	input();
	solve();
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000, INDEX = 1;
const int MAX_A = 1000000000, INF = MAX_A + 1;

int n, a[MAX_N + 1 + INDEX], ps[MAX_N + INDEX];

bool canAbsorb[MAX_N + 1 + INDEX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + INDEX, a + INDEX + n, less<int>());

    a[n + 1] = a[n];

    ps[0] = 0;
    for (int i = 1; i <= n; i++) {
        ps[i] = min(INF, ps[i - 1] + a[i]);
    }

    canAbsorb[n + 1] = true;
    for (int i = n; i >= 1; i--) {
        canAbsorb[i] = canAbsorb[i + 1] && a[i + 1] <= 2 * ps[i];
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (canAbsorb[i]) {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;

int main(){
    int b;
    while(cin>>b, b){
        for(int n = sqrt(b*2); n>=1; n--){
            int a = (b*2/n - n + 1)/2;
            if(a>0 && b*2==(a + a+n-1)*n){
                cout<<a<<" "<<n<<endl;
                break;
            }
        }
    }
}


Measured memory_bytes: 3016
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <math.h>
#include <map>
#include <stack>
using namespace std;
static const int INF = 1e9+7;
// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, a, b) for (int i =a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define PI 3.14159265359

int main(){
    int n; cin >> n;
    string s; cin >> s;

    int ans = 0;
    repr(i, 1, n){
        int cnt=0;

        for(char c='a'; c<='z'; c++){
            bool left = false, right = false;

            rep(j, i){
                if(s[j] == c) left=true;
            }

            for(int j=i; j<n; j++){
                if(s[j] == c) right=true;
            }

            if(left && right) cnt++;
        }

        if(ans < cnt) ans = cnt;

    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3604
/* Aditya0412 */
#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define pb push_back 
#define ve vector
#define vii vector < int >
#define vll vector < ll > 
#define pii pair < int , int >
#define pll pair < ll , ll >
#define vpl vector < pll >
#define fi first
#define all(a)      (a).begin(),(a).end()
#define si(x)       (int)((x).size())
#define debug(x)    cout<<#x<<" is "<<(x)<<endl;cout.flush();  
#define se second 
#define endl        '\n'
#define f(i,a,b)    for(int i=a;i<b;i++)
#define mem(a,x)          memset(a,x,sizeof(a))

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
    os<<"[";
    for(auto& x:v){os<<x<<", ";}
    return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===


// const ll mod=998244353;
const ll mod = 1000000000+7;
const ll N=1000000+6;
#define M_PI           3.14159265358979323846
void inp(ll *arr,ll n)
{
  for(int i=0;i<n;i++)
    cin>>arr[i];
}
void inp_mat(ll *arr,ll n,ll m)
{
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++)
        {
          ll x;cin>>x;
          *((arr+i*m) + j)=x;
        }
}
// syntax for inp_mat inp_mat((ll *)arr,n,m);
// int x2[]={+1,-1,+0,+0};
// int y2[]={+0,+0,+1,-1};
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //  #ifndef ONLINE_JUDGEc
    //   freopen ("INPUT.txt" , "r" , stdin);
    //   freopen ("OUTPUT.txt", "w" , stdout);
    // #endif 
    int t=1;
    // cin>>t;
    while(t--)
    {
         ll n;cin>>n;ll arr[n];inp(arr,n);
      ll x=0;
      f(i,2,n)
      x^=arr[i];
      if((arr[0]+arr[1]-x)%2!=0)
      cout<<"-1";
      else{
        ll y=(arr[0]+arr[1]-x)/2;
        dbg(y);
        if(y>arr[0] or y<0)
        cout<<"-1";
        else{
          ll ind=60;
          ll y1=y;
          ll y2=y;
          while(ind>=0)
          {
            dbg((ll)1<<ind);
            if((x&((ll)1<<ind))!=0)
            {
              if((y1& ((ll)1 <<ind))!=0)
              {
                cout<<"-1";
                return 0;
              }
              if(((ll)1<<ind)+y<=arr[0])
              {
                y+=((ll)1<<ind);
              }
              else
              {
                y2+=((ll)1<<ind);
              }
              
              
            }
            
            
            ind--;

          }
          dbg(y);
          if(y==0 )
          cout<<"-1";
          else
          cout<<arr[0]-y;
        }
      }

    }    
} 

Measured memory_bytes: 3648
let () = Scanf.scanf "%d %d\n" @@ fun n k ->
  let count_k = Array.make k 0 in
  for i = 1 to n do
    count_k.(i mod k) <- 1 + count_k.(i mod k)
  done;
  Printf.printf "%d\n" @@
  if k mod 2 = 0 then 
    count_k.(0) * count_k.(0) * count_k.(0)
    + count_k.(k / 2) * count_k.(k / 2) * count_k.(k / 2)
  else
    count_k.(0) * count_k.(0) * count_k.(0)


Measured memory_bytes: 3200
#include <bits/stdc++.h>

using namespace std;

#define DUMP(x) std::cout << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++ i)
#define ALL(r) r.begin(), r.end()
#define DUP(x, y) (((x) + (y) - 1) / (y))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")

using ll = std::int64_t;
using vint = std::vector<int>;
using vll = std::vector<ll>;
using pint = std::pair<int, int>;

constexpr std::int32_t INF = 1001001001;

string getStr(int p, int y) {
    string ps = to_string(p);
    string py = to_string(y);

    while (ps.length() < 6) {
        ps = "0" + ps;
    }
    while (py.length() < 6) {
        py = "0" + py;
    }
    return ps + py;
    
}

void Main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int,int,int>> pyi(m);
    rep(i, m) {
        int p, y;
        cin >> p >> y;
        pyi[i] = make_tuple(p, y, i);
    }
    sort(ALL(pyi));

    vector<pint> py(m);
    vint index(m);

    rep(i, m) {
        int a, b, c;
        
        tie(a, b, c) = pyi[i];
        py[i] = make_pair(a, b);
        index[i] = c;
    }

    int prev_num_p = -1;
    int num_y = 0;
    vector<string> ans(m);
    rep(i, m) {
        int num_p = py[i].first;
        if (num_p == prev_num_p)++num_y;
        else num_y = 1;
        
        ans[index[i]] = getStr(num_p, num_y);

        prev_num_p = num_p;
    }

    rep(i, m) {
        cout << ans[i] << endl;
    }

}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}



Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Maxn = 1000005;
ll a[Maxn];
ll p = 2;
ll qpow(ll y,int z,int p){
    y%=p;ll ans=1;
    for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
    return ans;
}
ll C(ll n,ll m){
    if(m>n)return 0;
    return ((a[n]*qpow(a[m],p-2,p))%p*qpow(a[n-m],p-2,p)%p);
}
ll Lucas(ll n,ll m){
    if(!m)return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}

ll N;
ll b[Maxn];
ll ans;
int main()
{
	a[1] =a[0] =  1;
	for(int i=2;i<Maxn;i++)	a[i] = (a[i-1] * i)%p;
	cin>>N;
	for(int i=1;i<=N;i++) scanf("%1lld",&b[i]);
	for(int i=1;i<N;i++) b[i] = abs(b[i] - b[i+1]);
	N--;
	bool HaveOne = false;
	for(int i=1;i<=N&&!HaveOne;i++) if(b[i] == 1) HaveOne = true;
	if(!HaveOne)	for(int i=1;i<=N;i++) b[i]/=2;
	for(int i=1;i<=N;i++)
	{
		ans += Lucas(N-1,i-1) * b[i];
		ans %= 2;
	}
	if(!HaveOne) ans *=2;
	cout<<ans;
	return 0;
}//奥里给

Measured memory_bytes: 15872
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
const int N=13;

template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

char s[N];
int n;
void dfs(int x,int cnt) {
	if(x==n) {puts(s);return ;}
	for(int i=0;i<cnt;i++) 
		s[x]=i+'a',dfs(x+1,cnt);
	s[x]=cnt+'a';dfs(x+1,cnt+1);
}

int main() {
	qr(n); dfs(0,0);
	return 0;
}



Measured memory_bytes: 1408
import java.util.*;

class Main {
    static final int I=1000000000;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n=scan.nextInt();
        int ma=scan.nextInt();
        int mb=scan.nextInt();
        int[]d=new int[n],c=new int[n];
        for(int i=0;i<n;++i){
            int a=scan.nextInt();
            int b=scan.nextInt();
            c[i]=scan.nextInt();
            d[i]=mb*a-ma*b;
        }
        int p=n/2;
        int[]f=new int[1<<p];
        int[]fc=new int[1<<p];
        int[]s=new int[1<<(n-p)];
        int[]sc=new int[1<<(n-p)];
        for(int i=0;i<1<<p;++i)
            for(int j=0;j<p;++j)
                if((i&1<<j)!=0){f[i]+=d[j];fc[i]+=c[j];}
        for(int i=1;i<1<<(n-p);++i)
            for(int j=0;j<n-p;++j)
                if((i&1<<j)!=0){s[i]+=d[p+j];sc[i]+=c[p+j];}
        Map<Integer,Integer>hm=new HashMap<Integer,Integer>();
        for(int i=1;i<1<<(n-p);++i){
            if(hm.containsKey(-s[i]))
                hm.put(-s[i],Math.min(hm.get(-s[i]),sc[i]));
            else
                hm.put(-s[i],sc[i]);
        }
        int m=I;
        for(int i=1;i<1<<(n-p);++i)
            if(s[i]==0)m=Math.min(m,sc[i]);
        for(int i=1;i<1<<p;++i){
            if(f[i]==0)m=Math.min(m,fc[i]);
            if(hm.containsKey(f[i]))
                m=Math.min(m,fc[i]+hm.get(f[i]));
        }
        System.out.println(m==I?-1:m);
    }
}


Measured memory_bytes: 78044
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = sc.nextInt();

        int answer = (x-z)/(y+z);
        System.out.println(answer);
    }
}

Measured memory_bytes: 21588
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

int main() {
  int N, C;
  cin >> N;
  vector<int> L(N);
  C = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> L.at(i);
  }
  
  sort(L.begin(), L.end());
  
  // a+b>c かつ b+c>a かつ c+a>b
  
  if (N >= 3) {
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        for (int k = j + 1; k < N; k++) {
          if (L.at(i) != L.at(j)) {
            if (L.at(i) != L.at(k)) {
              if (L.at(j) != L.at(k)) {
                if (L.at(i) + L.at(j) > L.at(k)) {
                  if (L.at(i) + L.at(k) > L.at(j)) {
                    if (L.at(j) + L.at(k) > L.at(i)) {
                      C = C + 1;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  
  cout << C;
 
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(i=a;i<n;i++)
#define test(a) cout << "*" << a << endl
#define ll long long
int main (){
  int i,j,k;
  int iMin;
  ll N,K;
  ll x[100000];
  ll xMin = 100000000;
  ll dist;
  ll distMin=10000000000000000;
  ll count=0;
  //ll xMax = 0;
  
  cin >> N >> K;
  rep(i,0,N){
    cin >> x[i];
    /*if(x[i]<=xMin){
      xMin = x[i];
    }*/
    /*else if(xMax<=x[i]){
      xMax = x[i];
    }*/
    if(0<=x[i] && x[i]<=xMin){/*注意：全て「ー」にある例外も考慮すべし*/
      xMin = x[i];
      iMin = i;
      //test(iMin);
    }
  }
  if(xMin == 100000000){/*これか？！*/
    iMin = N-1;
  }
  //test(xMin);
  //test(xMax);
  
  while(K+1>count && 0<=iMin){
    if(N-1 < iMin+(K-1)){
        iMin -= 1;
        count++;
        continue; 
    }    
    if(x[iMin+(K-1)]*x[iMin]>0){
      dist = max(abs(x[iMin+(K-1)]),abs(x[iMin]));
    }
    else{
      if( abs(x[iMin]) < abs(x[iMin+(K-1)]) ){
        dist = x[iMin+(K-1)] - x[iMin] + abs(x[iMin]);
      }
      else{
        dist = x[iMin+(K-1)] - x[iMin] + abs(x[iMin+(K-1)]);
      }      
    }
    if(dist<distMin){
      distMin = dist;
      //test(iMin);
    }    
    iMin -= 1;
    count++; 
  }
  
  cout << distMin << endl;
  
 

}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

struct query{
  ll type;//0=empty, 1=add-sum ,2=set-min
  ll value;
  query(ll a=0,ll b=0):type(a),value(b) {}
};

ll INF=(1LL<<60);

struct segtree{
  ll SIZE;
  vector<query> s;
  vector<ll> t;// sum-add
  vector<ll> u;// min-set

  segtree(ll n=1){
    SIZE=1;
    while(SIZE<n)SIZE*=2;
    s.clear();
    t.clear();
    u.clear();
    s.resize(SIZE*2, query());
    t.resize(SIZE*2, 0);
    u.resize(SIZE*2, 0);
  }
  
  void func(ll k,ll l,ll r,query q){
    if(q.type==1){
      if(s[k].type==0)s[k]=q;
      else s[k].value+=q.value;
      t[k]+=q.value*(r-l);
      u[k]+=q.value;
    }
    if(q.type==2){
      s[k]=q;
      t[k]=q.value*(r-l);
      u[k]=q.value;
    }
  }

  void compute(ll k,ll l,ll r){
    query q=s[k];
    s[k]=query();
    if(q.type==0||r-l==1)return;
    ll m=(l+r)/2;
    func(k*2+1,l,m,q);
    func(k*2+2,m,r,q);
  }

  void Update(ll a,ll b,query x,ll k,ll l,ll r){
    if(b<=l || r<=a)return;
    compute(k,l,r);
    if(a<=l && r<=b){
      func(k,l,r,x);
    }else{
      ll m=(l+r)/2;
      Update(a,b,x,k*2+1,l,m);
      Update(a,b,x,k*2+2,m,r);
      t[k]=t[k*2+1]+t[k*2+2];
      u[k]=min(u[k*2+1],u[k*2+2]);
    }
  }

  ll Dfs(ll type,ll a,ll b,ll k,ll l,ll r){
    if(b<=l || r<=a){
      if(type==1)return 0; //add
      if(type==2)return INF; // min
    }
    compute(k,l,r);
    if(a<=l && r<=b){
      if(type==1)return t[k];
      if(type==2)return u[k];
    }else{
      ll m=(l+r)/2;
      ll lv=Dfs(type,a,b,k*2+1,l,m);
      ll rv=Dfs(type,a,b,k*2+2,m,r);
      if(type==1)return lv+rv; // add
      if(type==2)return min(lv,rv); // min
    }
  }

  void Add(ll a,ll b,ll x){
    Update(a,b,query(1,x), 0,0,SIZE);
  }
  void Set(ll a,ll b,ll x){
    Update(a,b,query(2,x), 0,0,SIZE);
  }
  ll Getsum(ll a,ll b){
    return Dfs(1,a,b, 0,0,SIZE);
  }

  ll Getmin(ll a,ll b){
    return Dfs(2,a,b, 0,0,SIZE);
  }
  
};

int main() {
  ll n,k;
  cin >> n >> k;
  vec a(n+1);
  for(ll i=1;i<=n;i++) cin >> a[i],a[i]-=k;
  for(ll i=0;i<n;i++) a[i+1]+=a[i];
  vector<pll> b(n+1);
  for(ll i=0;i<=n;i++) {
    b[i]={a[i],i};
  }
  sort(b.begin(),b.end());
  ll ans=0;
  segtree T(n+1);
  T.Set(0,n+1,0);
  for(ll i=0;i<=n;i++) {
    ll id=b[i].second;
    ans+=T.Getsum(0,id);
    T.Add(id,id+1,1);
  }
  cout << ans << endl;
}

Measured memory_bytes: 24372
#![allow(unused_imports)]
#![allow(non_snake_case)]

use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter};
use std::io::*;
use std::ops::*;
use std::*;

// -----------------------------------------------
// Framework
// -----------------------------------------------

#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($arg:expr),*) => {
        #[cfg(debug_assertions)]
        {
            let entries = [$(&stringify!([$arg]:), &$arg as &Debug),*];
            stderr().write_fmt(format_args!("{:#?}\n", entries)).unwrap();
        }
    };
}

#[allow(dead_code)]
fn rl() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

// -----------------------------------------------
// Solution
// -----------------------------------------------

type V = (i64, i64, i64);

fn dot((sa, sb, sc): V, (x, y, z): V) -> i64 {
    sa * x + sb * y + sc * z
}

fn solve(N: usize, M: usize, t: &Vec<V>) -> i64 {
    let mut max_score = 0;

    for &sa in &[1, -1] {
        for &sb in &[1, -1] {
            for &sc in &[1, -1] {
                let S = (sa, sb, sc);
                let mut scores = Vec::new();
                for i in 0..N {
                    scores.push(dot(S, t[i]));
                }
                scores.sort();
                max_score = max(max_score, scores.into_iter().rev().take(M).sum());
            }
        }
    }
    max_score
}

pub fn main() {
    let (N, M) = read!(usize, usize);
    let t = read![i64, i64, i64; N];
    println!("{}", solve(N, M, &t));
    return;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n; cin >> n;
  string a, b, c; cin >> a >> b >> c;
  int res = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == b[i] and a[i] == c[i]) {

    } else if (a[i] != b[i] and a[i] != c[i] and b[i] != c[i]) {
      res += 2;
    } else {
      res += 1;
    }
  }
  cout << res << '\n';
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 1000
#define s(x,y) _s[x][y+maxn]
#define gg(x,y) _gg[x][y+maxn]
#define v2(x) _v2[x+maxn]
using namespace std;
typedef long long LL;
int read()
{
    char c=getchar();int f=1,sum=0;
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){sum=sum*10+c-'0';c=getchar();}
    return sum*f;
}
using namespace std;
char c[maxn][maxn];
LL _s[maxn][maxn+maxn];
int _gg[maxn][maxn+maxn],n,m;
struct P{int x,y;}a[maxn*maxn];
vector<P> v1[maxn],_v2[maxn+maxn];
inline int S(int x1,int y1,int x2,int y2)
{
	if(x1>x2||y1>y2||x1<2||x2>n+m||y1<1-m||y2>n-1) return 0;
	return s(x2,y2)-s(x2,y1-1)-s(x1-1,y2)+s(x1-1,y1-1);
}
inline bool cmp1(P x,P y){return x.y<y.y;}
inline bool cmp2(P x,P y){return x.x<y.x;}
int main()
{	
	int t=0; LL s1=0,s2=0; n=read();m=read();
	for(int i=1;i<=n;i++) scanf("%s",c[i]+1);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	if(c[i][j]=='#') a[++t]=P{i+j,i-j},v1[i+j].push_back(a[t]),v2(i-j).push_back(a[t]),gg(i+j,i-j)++;
	for(int i=2;i<=n+m;i++) sort(v1[i].begin(),v1[i].end(),cmp1);
	for(int i=1-m;i<=n-1;i++) sort(v2(i).begin(),v2(i).end(),cmp2);
	for(int i=2;i<=n+m;i++)
	for(int j=1-m;j<=n-1;j++) s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+gg(i,j);
	for(int i=2;i<=n+m;i++)
	for(int j=0;j<v1[i].size();j++)
	for(int k=j+1;k<v1[i].size();k++)
	{
		P x=v1[i][j],y=v1[i][k];
		int d=y.y-x.y;
		s1+=S(x.x+d,x.y+1,x.x+d,y.y-1)+S(x.x-d,x.y+1,x.x-d,y.y-1);
		s2+=S(x.x+d,x.y,x.x+d,x.y)+S(x.x+d,y.y,x.x+d,y.y)+S(x.x-d,x.y,x.x-d,x.y)+S(x.x-d,y.y,x.x-d,y.y);
	}
	for(int i=1-m;i<=n-1;i++)
	for(int j=0;j<v2(i).size();j++)
	for(int k=j+1;k<v2(i).size();k++)
	{
		P x=v2(i)[j],y=v2(i)[k];
		int d=y.x-x.x;
		s1+=S(x.x+1,x.y+d,y.x-1,x.y+d)+S(x.x+1,x.y-d,y.x-1,x.y-d);
		s2+=S(x.x,x.y+d,x.x,x.y+d)+S(y.x,x.y+d,y.x,x.y+d)+
			S(x.x,x.y-d,x.x,x.y-d)+S(y.x,x.y-d,y.x,x.y-d);
	}
	printf("%lld\n",s1+s2/2);
	return 0;
}


Measured memory_bytes: 23936
#include <bits/stdc++.h>

using namespace std;


#ifdef zxc

#include <sys/resource.h>
#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = int64_t;
using ld = long double;
const ld EPS = 1e-9;
//const ll MOD = 924844033;
const ld PI = 3.141592653589793;
const int maxn = 300001;
const ll MOD = 1e9 + 7;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

ll pw(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
    }
    return res;
}

template<typename Cont>
vector<vector<int>> accum2d(Cont a, int n, int m) {
    vector<vector<int>> res(n, vector<int>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            res[i][j] = a[i][j];
            if (i > 0) {
                res[i][j] += res[i - 1][j];
            }
            if (j > 0) {
                res[i][j] += res[i][j - 1];
            }
            if (i > 0 && j > 0) {
                res[i][j] -= res[i - 1][j - 1];
            }
        }
    }
    return res;
}

vector<vector<int>> resize2d(vector<vector<int>> a, int n, int m) {
    a.resize(n);
    for (auto &x:a) {
        x.resize(m);
    }
    return a;
}

int up[1030][1030];
int down[1030][1030];
int lft[1030][1030];
int rght[1030][1030];
int ans[1030][1030];
int pref[1030][1030];
int arifm[1030][1030];
int dp1[1030][1030];
int dp2[1030][1030];

signed main() {
#ifdef zxc
    struct rlimit rl;
    const rlim_t kStackSize = 512L * 1024L * 1024L;
    assert(!getrlimit(RLIMIT_STACK, &rl));
    rl.rlim_cur = kStackSize;
    assert(!setrlimit(RLIMIT_STACK, &rl));
    freopen("../kolya_input.txt", "r", stdin);
//    freopen("../kolya_output.txt", "w", stdout);
#else
    //    mt19937 mt(std::chrono::high_resolution_clock::now().time_since_epoch().count());
    //            freopen("", "r", stdin);
    //        freopen("hack.out", "w", stdout);
#endif
    auto solve = [](int _) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        vector<int> v;
        for (char c:s) {
            v.push_back(c == 'B' ? 1 : 0);
        }
        bool xx = true;
        for (int i = 2 * n - 1; i >= 0; --i) {
            if (xx) {
                v[i] ^= 1;
            }
            xx ^= 1;
        }
        ll cock = 1;
        ll cnt_zeros = 0;
        for (int i = 2 * n - 1; i >= 0; --i) {
            if (v[i]) {
                cock *= cnt_zeros;
                cock %= MOD;
                --cnt_zeros;
            } else {
                ++cnt_zeros;
            }
        }
        if (cnt_zeros) {
            cock = 0;
        }
        for (int i = 1; i <= n; ++i) {
            cock *= i;
            cock %= MOD;
        }
        cout << cock;
    };


    fast_io();
    cout.precision(9);
    cout << fixed;
    auto start = chrono::steady_clock::now();
    for (int i = 1; i <= 1; ++i)solve(i);
    auto end = chrono::steady_clock::now();

    debug("time", chrono::duration_cast<chrono::milliseconds>(end - start).count() / 1000.0);

}


Measured memory_bytes: 1680
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

char S;

void solve() {

	if (S == 'A') cout << 'T';
	if (S == 'T') cout << 'A';
	if (S == 'C') cout << 'G';
	if (S == 'G') cout << 'C';

	return;
}

int main() {

	cin >> S;

	solve();
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

void dfs(string& s, int i, int sum, string ans) {
    if (i == 3) {
        if (sum == 7) {
            cout << ans + "=7" << endl;
            exit(0);
        }
        return;
    }
    dfs(s, i + 1, sum + (s[i + 1] - '0'), ans + "+" + string(1, s[i + 1]));
    dfs(s, i + 1, sum - (s[i + 1] - '0'), ans + "-" + string(1, s[i + 1]));
}

void _main() {
    string s;
    cin >> s;
    dfs(s, 0, s[0] - '0', s.substr(0, 1));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}

Measured memory_bytes: 256