akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll pow(ll x,ll n){
  ll res=1;
  while(n>0){
    if(n & 1){
      res*=x;
      x*=x;
      n >>= 1;
    }
  }
  return res;
}

pair<int,int> ftoS(int x){
  if(x==0){
    return make_pair(1,0);
  }
  else if(x==1){
    return make_pair(1,1);
  }
  else if(x==2){
    return make_pair(0,0);
  }
  else if(x==3){
    return make_pair(0,1);
  }
}

int main(){
  ll N;
  cin >> N;
  ll k;
  vector<int> four;
  vector<int> S;
  if(N==0){
    cout << 0 << endl;
    return 0;
  }
  else if(N>0){
    ll p=1;
    ll l=0;
    while(p<3*N-1){
      p*=4;
      l++;
    }
    k=2*l-1;
    N+=2*(pow(2,k+1)-1)/3;
    for(int i=0;i<=(k-1)/2;i++){
      four.push_back(N%4);
      N/=4;
    }
  }
  else if(N<0){
    ll p=1;
    ll l=0;
    while(2*p<-3*N+2){
      p*=4;
      l++;
    }
    k=2*l;
    N+=2*(pow(2,k)-1)/3;
    for(int i=0;i<=k/2-1;i++){
      four.push_back(N%4);
      N/=4;
    }
  }
  for(int i=(int)four.size()-1;i>=0;--i){
    S.push_back(ftoS(four[i]).first);
    S.push_back(ftoS(four[i]).second);
  }
  bool flag=false;
  for(int x:S){
    if(!flag && x==0){
      continue;
    }
    if(x!=0){
      flag=true;
    }
    cout << x;
  }
  cout << endl;
}

Measured memory_bytes: 4076
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int t=b;
		int j=1;
		int ab;
		while(t>0) {
			if(t/10>=1) {
				j++;
			}
			t=t/10;
		}
		for(int i=1;i<=j;i++) {
			a=a*10;
		}
		ab=a+b;
		for(int i=1;i<=ab/2;i++) {
			if(ab==i*i) {
				System.out.println("Yes");
				break;
			}
			else if(ab!=i*i&&i==ab/2){
				System.out.println("No");
			}
		}
	}

}


Measured memory_bytes: 21076
#include<bits/stdc++.h>
using namespace std;
int n,k,ans,i,j;
string s;
int main(){
	cin>>n>>k>>s;
	while(j<n){
		while(j<n&&s[j]=='1')++j;
		ans=max(ans,j-i);
		while(j<n&&s[j]=='0')++j;
		--k;
		if(k<0){
			while(i<n&&s[i]=='1')++i;
			while(i<n&&s[i]=='0')++i;
		}
		ans=max(ans,j-i);
	}
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;
const int N = 1e5 + 5;
int ps[N], ps2[N], n, q;
string s;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s, n = s.size();
    for (int i = 1; i <= n; i++) {
        ps[i] = ps[i - 1];
        if (s[i - 1] == 'A') ps[i] += 1;
        else ps[i] += 2;
    }
    cin >> s, n = s.size();
    for (int i = 1; i <= n; i++) {
        ps2[i] = ps2[i - 1];
        if (s[i - 1] == 'A') ps2[i] += 1;
        else ps2[i] += 2;
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r, l2, r2; cin >> l >> r >> l2 >> r2;
        cout << ((ps[r] - ps[l - 1]) % 3 == (ps2[r2] - ps2[l2 - 1]) % 3 ? "YES" : "NO") << "\n";
    }

    return 0;
}


Measured memory_bytes: 4576
s = input()
k = int(input())
ans = 0

sum_num = 0
for i in range(len(s)):
    num = int(s[i])
    if num == 1:
        sum_num += 1
        if sum_num >= k:
            ans = 1
            break
    else:
        ans = num
        break

print(ans)

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;
#define INF 1000000000;

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> xm,xp;
  for(int i=0;i<N;i++){
    int temp;
    cin >> temp;
    if(temp<0){
      xm.push_back(-temp);
    }else if(temp>0){
      xp.push_back(temp);
    }else{
      K--;
    }
  }
  reverse(xm.begin(),xm.end());
  /*for(auto itr = xm.begin(); itr!=xm.end(); itr++){
    cout << *itr << " ";
  }
  cout << endl;
  for(auto itr = xp.begin(); itr!=xp.end(); itr++){
    cout << *itr << " ";
  }
  cout << endl;*/

  if(xm.size()==0 && xp.size()==0){
    cout << 0 << endl;
    return 0;
  }


  int ans = INF;
  //右にのみ
  if(xp.size()>=K){
    ans = min(ans, xp[K-1]);
  }
  //左のみ
  if(xm.size()>=K){
    ans = min(ans, xm[K-1]);
  }

  //みぎから左
  for(int i=1;i<=K-1;i++){
    if(xp.size()>=i && xm.size()>=K-i){
      ans = min(ans, 2*xp[i-1]+xm[K-i-1]);
    }
  }
  //左から右
  for(int i=1;i<=K-1;i++){
    if(xm.size()>=i && xp.size()>=K-i){
      ans = min(ans, 2*xm[i-1]+xp[K-i-1]);
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main() {
  int N;
  cin >> N;
  vi t(N+1), x(N+1), y(N+1);
  t[0]=0;
  x[0]=0;
  y[0]=0;
  rep(i, N) cin >> t[i+1] >> x[i+1] >> y[i+1];

  rep(i, N) {
    if (t[i+1] - t[i] < abs(x[i+1] - x[i]) + abs(y[i+1] - y[i])) {
      cout << "No" << endl;
      return 0;
    }

    if ((t[i] + x[i] + y[i]) % 2 != 0) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 4580
#include<stdio.h>

void swap(long *a,long *b){
	long tmp = *a;
	*a = *b;
	*b = tmp;
}

int main(void){
	long a,b;
	while(scanf("%ld %ld",&a,&b)!= EOF){
		if(a < b) swap(&a,&b);
		long r = a % b;
		long product = a * b;
		while(r != 0){
			a = b;
			b = r;
			r = a % b;
		}
		printf("%ld %ld\n",b,product/b);
	}
	return 0;
}

Measured memory_bytes: 596
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use itertools_num::ItertoolsNum;
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::iter;
#[allow(unused_imports)]
use superslice::*;

fn run() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let l = sc.read_vec::<usize>(n);

    let mut ans = 0usize;
    for i in 0..n {
        for j in i + 1..n {
            for k in j + 1..n {
                if l[i] != l[j]
                    && l[j] != l[k]
                    && l[i] != l[k]
                    && l[i] + l[j] > l[k]
                    && l[i] + l[k] > l[j]
                    && l[k] + l[j] > l[i]
                {
                    ans += 1;
                }
            }
        }
    }
    println!("{}", ans);
}

fn main() {
    std::thread::Builder::new()
        .name("run".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(run)
        .unwrap()
        .join()
        .unwrap();
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn read_pairs<T: std::str::FromStr>(&mut self, n: usize) -> Vec<(T, T)> {
        (0..n).map(|_| (self.read(), self.read())).collect()
    }
    pub fn read_pairs_1_indexed(&mut self, n: usize) -> Vec<(usize, usize)> {
        (0..n)
            .map(|_| (self.read::<usize>() - 1, self.read::<usize>() - 1))
            .collect()
    }
    pub fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    pub fn read_char_grid(&mut self, n: usize) -> Vec<Vec<char>> {
        (0..n).map(|_| self.read_chars()).collect()
    }
    pub fn read_matrix<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n)
            .map(|_| (0..m).map(|_| self.read()).collect())
            .collect()
    }
}


Measured memory_bytes: 2240
#!/usr/bin/env python3

S = input()
K = int(input())

if len(S) == 1:
    print(K//2)
    exit()

cnt = 1
C = []
for i in range(1,len(S)):
    if S[i-1] == S[i]:
        cnt += 1
    else:
        C.append([S[i-1], cnt])
        cnt = 1
C.append([S[i], cnt])

ans = 0
if len(C) == 1:
    print((C[0][1]*K) // 2)
    exit()
else:
    for c in C:
        ans += c[1] // 2

ans *= K

ans2 = 0
if S[-1] == S[0]:
    ans2 = ((C[0][1]+C[-1][1])//2 - C[0][1]//2 - C[-1][1]//2) * (K-1)
print(ans + ans2)


Measured memory_bytes: 3064
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)
N = input()

if N < 105:
    print 0
elif N < 135:
    print 1
elif N < 165:
    print 2
elif N < 189:
    print 3
elif N < 195:
    print 4
else:
    print 5

Measured memory_bytes: 2808
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
void chmin(LL& a, LL b) {
	a = min(a, b);
}
//////////////

void solve() {
	int N, i;
	cin >> N >> i;
	cout << N - i + 1 << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
while True:
    #審判の数
    n = int(input())
    if n == 0:
        break
    a = [0]*n               #空いてる配列
    for i in range(n):       #空いてる配列に点数を入れる
        s = int(input())
        a[i] = s
    tensu = (sum(a) - min(a) -max(a))/(len(a)-2) #一番でかい点数と一番小さい点数は一つずつ引いて平均
    print(int(tensu))        #平均点！


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

int main(){
	string s;
	cin>>s;
	
	int st=-2,g=-2;
	for(int i=1;i<s.size();i++){
		if(s[i]==s[i-1]){
			st=i-1,g=i;
			}
		}
		
	for(int i=2;i<s.size();i++){
		if(s[i]==s[i-2]){
			st=i-2,g=i;
			}
		}	
		cout<<st+1<<' '<<g+1<<endl;
	}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <string.h>
#include <vector>
//s#define rep(i, n) for (int i = 0; i < (n); i++)
#define MAX 10000

using namespace std;

#define ll long long
#define pb push_back
//#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a; i<n; i++)
#define r0 return 0
#define INF (int)1e15
#define MOD 1000000007
//#define N 12
#define sz 1000*1000

 int main(){

 int n; cin>>n;
  vector<pair<int,int>>v(n);

  for(int i=0;i<n;i++){
   cin>>v[i].second>>v[i].first;
  }

  sort(v.begin(),v.end());

  int sum =0;
  bool ans = true;

  for(vector<pair<int,int>>::iterator it = v.begin();it!=v.end();it++)
  {
      sum += it->second;
      if(sum > it->first){
            ans = false;
            break; }
  }

  if(ans == false)
      cout<<"No"<<endl;
  else
      cout<<"Yes"<<endl;

 return 0;
 }


Measured memory_bytes: 4820
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mp(x,y)     make_pair(x,y) 
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,a,n)   for(ll i=a;i<n;i++)
#define frr(i,a,n)  for(ll i=n-1;i>=a;i--)


const ll N   =  500005;
const ll mod = 1e9 + 7;

using namespace std;


void solve()
{
// string s;
  ll n,m,k,x=0,y=0,c=0,q,ans=0;
  cin>>n>>x;
  ll a[n],d[n+1];
d[0] = 0;
  for (ll i = 0; i < n; ++i)
  {
  cin>>a[i];
  d[i+1] = d[i] + a[i];
  }
  for (int i = 0; i < n+1; ++i)
  {
    if(d[i]<=x)
      c++;
  }

  
  cout<<c<<" ";
}

signed main(){

      ios_base::sync_with_stdio(false);   
      cin.tie(NULL);
      ll T=1;
      //cin>>T;
      while(T--)
      {
      solve();
      }
      return 0;
    }


Measured memory_bytes: 256
program main
implicit none
integer :: i, j, k, n, q
integer , allocatable :: a(:), b(:)

read(*,*) n, k, q
allocate( a(q), b(n) )
b = 0
do i = 1, q
   read(*,*) a(i) 
   b( a(i) ) = b( a(i) ) + 1
end do
do i = 1, n
   if( q - b(i) .ge. k ) then
      write(*,*) 'No'
   else
      write(*,*) 'Yes'
   end if
end do

end program main

Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++)
    cin >> A[i];

  vector<int> v;
  for (int i = 0; i < N; i++) {
    auto it = upper_bound(v.begin(), v.end(), -A[i]);
    if (it == v.end())
      v.push_back(-A[i]);
    else
      *it = -A[i];
  }

  cout << v.size() << endl;
}


Measured memory_bytes: 1276
def main():
    n=int(input())
    ab=[]
    cd=[]
    for _ in range(n):
        ab.append(list(map(int,input().split())))
    for _ in range(n):
        cd.append(list(map(int,input().split())))
    ab.sort(reverse=True , key=lambda y:y[1])
    cd.sort(key=lambda y:y[0])
    ans=0
    for i in range(n):
        [x,y]=cd[i]
        for j in range(len(ab)):
            if x>ab[j][0] and y>ab[j][1]:
                ab.pop(j)
                ans+=1
                break
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 38640
#include <iostream>

using namespace std;

#include<string.h>

int main()
{
    char f;
    char l;
    int b;
    string c;
    cin>>c;
   f=c[0];
   l=c.length();
   b=l-2;
   cout<<f<<b<<c[l-1];
   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<cstring>
#include<math.h>
#include<iomanip>
#include<vector>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<cctype>
#include<utility>
#include<set>
#include<map>
#include<sstream>
#include<iterator>
#include<limits>
#include<map>
#include<deque>
using namespace std;
#define pb push_back
#define F(i,a,b) for(int i=a;i<b;++i)
#define Fl(i,a,b) for(long long i=a;i<b;++i)
#define all(v) v.begin(), v.end() 
#define X first;
#define Y second;
#define mp make_pair;
typedef long long ll;
typedef std::vector<int> vec;
typedef std::vector<long long> vecl;
typedef map<int,int> mii;
typedef std::pair<int,int> pii;
typedef pair<ll,ll> pll; 
const int MOD = 1000000007;


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

// 	int t{},T{};
// 	cin>>t;T=t;
// 	while(t--){
        //cout<<"------------- #"<<T-t<<endl;
        int n{},m{},k{},a{},b{},c{},f{},q=0;
        cin>>n;
        if(n>=30){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
        
 //   }
    
    
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main(){
  int n,m;
  int a=0,b=0,temp=0;
  int s[111];
  cin >> n >> m;
  for(int i=0;i<n;i++){
    cin >> s[i];
  }
  for(int i=1;i<=m;i++){
    for(int j=0;j<n-1;j++){
      a=s[j]%i;
      b=s[j+1]%i;
      if(a>b){
        temp=s[j];
        s[j]=s[j+1];
        s[j+1]=temp;
      }
      a=0;
      b=0;
    }
  }
  for(int i=0;i<n;i++){
    cout << s[i] << endl;
  }
  return (0);
}



Measured memory_bytes: 3064
// Problem : A - Rainy Season
// Contest : AtCoder - AtCoder Beginner Contest 175
// URL : https://atcoder.jp/contests/abc175/tasks/abc175_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define fr(i,a,b) for(int i=a;i<b;i++)
#define frr(i,a,b) for(int i=a;i>=b;i--)
//vector
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pp pop_back
//pair
#define pi pair<int ,int >
#define mk make_pair
#define ff first
#define ss second
//set
#define si set<int>
#define sit set<int>::iterator 
using namespace std;
int main()
{
	/*
	#ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
	#endif
	*/
fast;
string  s;cin>>s;
int cnt=0,ans=0;
char cmp='R';
fr(i,0,s.size())
{
	if(s[i]==cmp) cnt++;
	else 
	{
		ans=max(ans,cnt);
		cnt=0;
	}
}
cout<<max(ans,cnt);
return 0;
}

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

int main(){
  int n; cin >> n;
  std::vector<int> v(100,0);
  for (int i = 0; i < n; i++) {
    /* code */
    int d; cin >> d;
    v[d-1] = 1;
  }
  int ans =0;
  for (int i = 0; i < 100; i++) {
    /* code */
    ans += v[i];
  }
  std::cout << ans << '\n';
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")

#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/rope"

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define pb push_back
#define sz size
#define f first
#define s second

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

struct custom_hash 
{
    static uint64_t splitmix64(uint64_t x) 
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const 
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> w(n);
    F0R(i, n) cin >> w[i];
    int res = INT_MAX;
    F0R(t, n - 1)
    {
        int s1 = 0;
        int s2 = 0;
        F0R(i, t + 1) s1 += w[i];
        FOR(i, t + 1, n) s2 += w[i];
        res = min(res, abs(s1 - s2));
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    int d[N];
    for (int i = 0; i < N; i++)
    {
        cin >> d[i];
    }
    sort(d, d + N);
    int ans = 0;
    for (int i = d[0]; i <= d[N - 1]; i++)
    {
        int lb = lower_bound(d, d + N, i) - d;
        if (lb == N - lb)
        {
            ++ans;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

int main()
{

	long long A, B, C, K, sum;

	cin >> A >> B >> C >> K;

	if (K <= A)
		sum = K;
	else if (A < K && K < A + B)
		sum = A;
	else if (A + B <= K && K <= A + B + C)
		sum = A - (K - A - B);

	cout << sum << endl;
}


Measured memory_bytes: 3640
import java.io._
import java.util.StringTokenizer
import scala.util.control.Breaks.{breakable,break}

object Main extends App {
  val in = new InputReader(System.in)
  val pw = new PrintWriter(System.out)

  // val a = new Array[Int](N)

  // val n = in.next().toInt
  // val a, b = in.next().toInt
  // val s = in.next()

  val H, W = in.next().toInt
  val S = new Array[String](H+1)
  for (i <- 1 to H)
    S(i) = "#" + in.next()

  //
  val wall = '#'

  val dpRow = Array.ofDim[Int](H+1, W+1)
  for (y <- 1 to H) {
    var cnt = 0
    for (x <- 1 to W) {
      if (S(y)(x) != wall) {
        cnt += 1
        if (x == W)
          dpRow(y)(x) = cnt
      }
      else {
        dpRow(y)(x) = cnt
        cnt = 0
      }
    }
  }

  for (y <- 1 to H) {
    var now = 0
    for (x <- (1 to W).reverse) {
      if (dpRow(y)(x) != 0) {
        now = dpRow(y)(x)
      }
      else {
        dpRow(y)(x) = now
      }
    }
  }


  //
  val dpCol = Array.ofDim[Int](H+1, W+1)
  for (x <- 1 to W) {
    var cnt = 0
    for (y <- 1 to H) {
      if (S(y)(x) != wall) {
        cnt += 1
        if (y == H)
          dpCol(y)(x) = cnt
      }
      else {
        dpCol(y)(x) = cnt
        cnt = 0
      }
    }
  }

  for (x <- 1 to W) {
    var now = 0
    for (y <- (1 to H).reverse) {
      if (dpCol(y)(x) != 0) {
        now = dpCol(y)(x)
      }
      else {
        dpCol(y)(x) = now
      }
    }
  }


  //
  var ans = 0L
  for (y <- 1 to H) {
    for (x <- 1 to W) {
      if (S(y)(x) != wall) {
        ans = Math.max(ans, dpRow(y)(x) + dpCol(y)(x) - 1)
      }
    }
  }

  println(ans)
}


class InputReader(stream: InputStream) {
  private val reader = new BufferedReader(new InputStreamReader(stream))
  private var tokenizer: StringTokenizer = new StringTokenizer(reader.readLine())
  def next(): String = {
    while (!tokenizer.hasMoreTokens()) {
      tokenizer = new StringTokenizer(reader.readLine())
    }
    tokenizer.nextToken()
  }
}


Measured memory_bytes: 95220
#include <iostream>

const int MOD = 1000000007;

int main(){
   int N;
   std::cin >> N;
   std::string S;
   std::cin >> S;

   long long ans = 1;
   long long left = 0;
   for(int i=0; i<N*2; ++i){
      if(left%2==1) S[i] = (S[i]=='B' ? 'W' : 'B');
      if(S[i]=='B') ++left;
      else ans = ans * (left--) % MOD;
   }
   if(left==0) {
      for(int i=1; i<=N; ++i) ans = ans * i % MOD;
      std::cout << ans%MOD << std::endl;
   } else {
      std::cout << 0 << std::endl;
   }

   return 0;

}


Measured memory_bytes: 644
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

int main(void) {
  long A, B, T;
  cin >> A >> B >> T;
  cout << B * (T / A) << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

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()-1;
        }
        sc.close();

        int count = 0;
        for(int i = 0; i < N; i++){
            if(a[a[i]] == i)
                count++;
        }
        System.out.println(count/2);
   }
}

Measured memory_bytes: 51668
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

struct Node{
	int p, l, r;
	int s, d, h;
};

struct Node bt[100005];
int n;
int root;

int calc_depth (int curr, int depth )
{
	if (curr == root ) return depth;
	return calc_depth (bt[curr].p, depth + 1);
}

int calc_sibling (int id )
{
	if (id == root ) return -1;

	int parent = bt[id].p;
	if (bt[parent].l == id ){
		return bt[parent].r;
	}else{
		return bt[parent].l;
	} // end if
}

int calc_degree (int id )
{
	int res = 0;
	if (bt[id].l != -1 ) res++;
	if (bt[id].r != -1 ) res++;

	return res;
}

int calc_height (int id, int ch )
{
	int res = 0;
	if (bt[id].l != -1 ) res = max (res, calc_height (bt[id].l, ch + 1 ) );
	if (bt[id].r != -1 ) res = max (res, calc_height (bt[id].r, ch + 1 ) );

	res = max (res, ch );

	return res;
	
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin >> n;

	rep (i, n ) bt[i].p = -1, bt[i].l = -1, bt[i].r = -1, bt[i].s = -1, bt[i].d = -1, bt[i].h = 0;

	rep (i, n ){
		int id, left, right;
		cin >> id >> left >> right;
		bt[left].p = id;
		bt[right].p = id;
		bt[id].l = left;
		bt[id].r = right;
	} // end rep
	rep (i, n ){
		if (bt[i].p == -1 ){
			root = i;
			break;
		} // end if
	} // end rep

	rep (i, n ) bt[i].s = calc_sibling (i );
	rep (i, n ) bt[i].d = calc_depth (i, 0 );
	rep (i, n ) bt[i].h = calc_height (i, 0 );

	rep (i, n ){
		printf ("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", i, bt[i].p, bt[i].s, calc_degree(i ), bt[i].d, bt[i].h  );	
		if (bt[i].p == -1 ){
			printf ("root\n" );
		}else
		if (bt[i].l == -1 && bt[i].r == -1 ){
			printf ("leaf\n" );
		}else{
			printf ("internal node\n" );
		} // end if
	} // end rep			

	return 0;
}

Measured memory_bytes: 1204
n,W=map(int,input().split())
vw=[]
for i in range(n):
    v,w=map(int,input().split())
    vw.append([v,w])
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(W+1):
        v,w=vw[i-1]
        if j>=w:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][W])


Measured memory_bytes: 25500
main () {
  int n, min = 1000000, max = -1000000;
  long int sum = 0;

  scanf("%d", &n);

  while(n--) {
    int a;
    scanf("%d", &a);
    if (a < min) min = a;
    if (a > max) max = a;
    sum += a;
  }

  printf("%d %d %ld\n", min, max, sum);
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(void) {
	int n,i;
	cin >> n;
	vector<int> a(n), b;
	rep(i, n) {
		cin >> a[i];
	}
	
	for (i = n - 1; i >= 0; i -= 2) {
		b.push_back(a[i]);
	}
	if (n % 2 == 0)	i = 0;
	else			i = 1;
	for (; i < n; i += 2) {
		b.push_back(a[i]);
	}
	rep(i, n-1) {
		cout << b[i] << " ";
	}
	cout << b[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 5076
import sys
input = sys.stdin.readline

def make_fact_list(n, MOD):
    # make factorial list from 0 to n
    fact = [0] * (n+1)
    inv = [0] * (n+1)
    factinv = [0] * (n+1)

    fact[0]=fact[1]=1
    inv[1]=1
    factinv[0]=factinv[1]=1

    for i in range(2,n+1):
        fact[i] = fact[i-1] * i % MOD
        inv[i] = MOD - (( inv[MOD % i] *  (MOD // i)) % MOD )
        factinv[i] = factinv[i-1] * inv[i] % MOD
    
    return fact, factinv

def cbn(n, k, MOD, fact = [], factinv = []):
    if len(fact) == 0 and len(factinv) == 0:
        fact, factinv = make_fact_list(n, MOD)
    return fact[n] * factinv[n-k] * factinv[k] % MOD


MOD = pow(10, 9) + 7
x, y = list(map(int, input().split()))

if (2*x-y) % 3 != 0 or (2*y-x) % 3 != 0:
    print(0)
elif (2*x-y) // 3 < 0 or (2*y-x) // 3 < 0:
    print(0)
else:
    s = (2*x-y) // 3
    t = (2*y-x) // 3

    fact, factinv = make_fact_list(s + t + 1, MOD)
    print(cbn(s+t, s, MOD, fact, factinv) % MOD)

Measured memory_bytes: 79724
#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    double r;
    const double pi = 3.141592653589793;
    double a = 0.0, l = 0.0; //結果
    
    cin >> r;
    
    a = r * r * pi;
    l = 2 * r * pi;
    
    printf("%f %f\n", a, l);
    
    return 0;
}


Measured memory_bytes: 3208
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
//#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define maxe max_element
#define mine min_element
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<ll,ll>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define SIZE 5000 + 1
const ll MAX=1e9;
const ll mod=1e9+7;

ll expo(ll x,ll n,ll M=mod){
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}

vl adj[200001];
const ll MaxSize = 3e5;
ll facts[MaxSize], invFacts[MaxSize];

void preproc() {
  facts[0] = 1;
  for (int i = 1; i < MaxSize; i++) {
    facts[i] = ((ll)facts[i - 1] * i) % mod;
  }
  invFacts[MaxSize - 1] = expo(facts[MaxSize - 1], mod - 2,mod);

  for (int i = MaxSize - 2; i >= 0; i--) {
    invFacts[i] = ((ll)invFacts[i + 1] * (i + 1)) % mod;
  }
}

ll combination(ll n, ll k) {
  if(n<k) return 0;
  ll res = facts[n];
  res = ((ll)res * invFacts[k]) % mod;
  return ((ll)res * invFacts[n - k]) % mod;
}
void solve()
{
    ll n,k,i;
    //preproc();
    cin>>n>>k;
    ll ans=0;
   fs(i,k,n+2)
   {
       ll left=((i-1)*i)/2;
       ll temp=n-i;
       ll right=((n*(n+1))/2)-((temp*(temp+1))/2);
       //debug4(i,left,right,temp);
       ans+=right-left+1;
       ans%=mod;

   }
   cout<<ans<<endl;

}

int main()
{
  boost;
  ll t=1;
 // cin>>t;
  while(t--)
  {

      solve();
  }
}


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

int main(void)
{
  long long N, K;
  cin >> N >> K;

  if (N > K)
  {
    N = N % K;
  }

  long long temp;
  while (true)
  {
    temp = llabs(N - K);
    if (N > temp)
    {
      N = temp;
    }
    else
    {
      break;
    }
  }
  cout << N << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,k,diff,flag=0;
    cin>>n>>k;
   // cout<<diff<<endl;
   //cout<<n%k<<endl;
   while(1)
   {
       if(n%k==0)
        {flag=1;
        break;}
       else
        diff=n%k;
        //cout<<diff<<endl;
        if(diff>k)
        {
            n=n%k;
        }
        else
        {
            n=n%k;
            break;
        }

   }
   //cout<<n<<endl;
   if (flag==1)
    cout<<"0"<<endl;
   else
    {
        while(1)
    {

        if(abs(n-k)>n)
        {
            cout<<n<<endl;
            break;
        }
        else if(abs(n-k)<n)
        {
            //diff=abs(n-k);
            n=abs(n-k);
            //cout<<n<<endl;
        }
    }
    }
}


Measured memory_bytes: 256
MOD = 1000000007
class ModInt(int):
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)

    def __sub__(self, other):
        return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)

    def __mul__(self, other):
        return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)

    def __floordiv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, MOD - 2, MOD))
        else:
            if other == 0:
                raise ZeroDivisionError
            else:
                return ModInt(self.x * pow(other, MOD - 2, MOD))

    def __pow__(self, other):
        return ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, MOD))

    __radd__ = __add__

    def __rsub__(self, other):
        return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)

    __rmul__ = __mul__

    def __rfloordiv__(self, other):
        return ModInt(other.x * pow(self.x, MOD - 2, MOD)) if isinstance(other, ModInt) else ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, MOD))

def main():
    n = int(input())
    A = list(map(lambda x: ModInt(int(x)), input().split()))
    print((sum(A) ** 2 - sum(a ** 2 for a in A)) // 2)



if __name__ == '__main__':
    main()



Measured memory_bytes: 66896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  string ans = "YES";
  
  vector<ll> a(n);
  rep(i, 0, n)
    cin >> a.at(i);
  sort(all(a));
  
  rep(i, 0, n-1) {
    if(a.at(i) == a.at(i+1)) {
      ans = "NO";
      break;
    }
  }
  
  cout << ans << "\n";

}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main() {
    double a,b,c,r,h,s;
    cin >> a >> b >> r;
    r = r /180.0 * M_PI;
    c = sqrt(a*a+b*b-2*a*b*cos(r));
    h = b * sin(r);
    s = a * h / 2.0;
    printf("%lf\n%lf\n%lf\n",s,a+b+c,h);
}


Measured memory_bytes: 3560
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    p = [0]*n
    f = [0]*n
    for i in range(m):
        a,b = input().split()
        a = int(a)-1
        if b == "WA" and not f[a]:
            p[a] += 1
        if b == "AC":
            f[a] = 1
    p = [p[i]*f[i] for i in range(n)]
    print(sum(f),sum(p))
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 52440
#include "bits/stdc++.h"
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
#define INF 100000000
typedef long long ll;

using namespace std;

int main()
{
    int n;
    bool flag = true;
    cin >> n;
    int t = 0, tnext, x = 0, xnext, y = 0, ynext;
    REP(i, n) {
        cin >> tnext >> xnext >> ynext;
        int time = tnext - t - abs(xnext - x) - abs(ynext - y);
        if (time < 0 || time % 2) {
            flag = false;
        }
        t = tnext;x = xnext;y = ynext;
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>

void insertion_sort(std::vector<int>& arr, int g, int& cnt)
{
  for (int i = g; i < arr.size(); i++) {
    int val = arr[i];
    int j = i - g;
    while (j >= 0 && arr[j] > val) {
      arr[j + g] = arr[j];
      j -= g;
      cnt++;
    }
    arr[j + g] = val;
  }
}

void generate_g(std::vector<long long>& G, int n)
{
  long long g = 1;
  do {
    G.push_back(g);
    g = (g * 3) + 1;
  }
  while (g < n && G.size() < 100);
  std::sort(G.begin(), G.end(), std::greater<long long>());
}

std::pair< std::vector<long long>, int >
shell_sort(std::vector<int>& arr)
{
  int cnt = 0;
  std::vector<long long> G;
  generate_g(G, arr.size());
  for (int i = 0; i < G.size(); i++) {
    insertion_sort(arr, G[i], cnt);
  }
  return std::make_pair(G, cnt);
}

int main()
{
  int N;
  std::vector<int> arr;

  scanf("%d", &N);
  arr.resize(N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);
  }

  std::pair< std::vector<long long>, int >
  result = shell_sort(arr);

  int M = result.first.size();
  printf("%d\n", M);

  for (int i = 0; i < M; i++) {
    if (i == M - 1) {
      printf("%lld\n", result.first[i]);
    }
    else {
      printf("%lld ", result.first[i]);
    }
  }

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

  for (int i = 0; i < arr.size(); i++) {
    printf("%d\n", arr[i]);
  }

  return 0;
}



Measured memory_bytes: 6312
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int w, n, a, b,c;
	vector<int> s;
	cin >> w >> n;
	for (int j = 1; j <= w; j++) {
		s.push_back(j);
	}
	for (int i = 0; i < n; i++) {
		(cin >> a).ignore() >> b;
		c = s[a - 1];
		s[a - 1] = s[b - 1];
		s[b - 1] = c;
	}
	for (int k = 0; k < w; k++) {
		cout << s[k] << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
N = int(input())
lis = [int(input()) for _ in range(N)]
lis_c = lis.copy()

mx1 = max(lis_c)
lis_c.remove(mx1)
mx2 = max(lis_c)

for i in lis:
    if i == mx1:
        print(mx2)
    else:
        print(mx1)


Measured memory_bytes: 14068
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
int main(void)
{
    string s,rs;
    cin >> s;
    int n = s.length();
    rs = s;
    reverse(rs.begin(), rs.end());
    bool flag = true;
    if (s == rs){
        int offset;
        offset = (n-1)/2;
        for(int i=0; i<offset; i++){
            if (s[i] != s[offset-1-i])   flag = false;
        }
        offset = (n+3) / 2;
        for(int i=offset-1; i<n; i++){
            if (s[i] != s[n-1-i]) flag = false;
        }
    }
    else flag = false;
    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
class Program
 {
   static void Main(string[] args)
   {
     string[] AB;
     AB = Console.ReadLine().Split(' ');
 
     int A,B,ans;
     A = int.Parse(AB[0]);
     B = int.Parse(AB[1]);
 
     ans = A-B+1;
     Console.WriteLine(ans);
     
         
   }
 }

Measured memory_bytes: 11092
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
//typedef pair<int,int> P;
//priority_queue<int> pque;
//priority_queue<int, vector<int>, greater<int>> pque;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2000000000;//10^9
ll MOD  = 1000000007;

int main(void){
    int N,T;
    cin >> N >> T;
    vector<int> c(N), t(N);
    for(int i = 0; i < N; i++){
        cin >> c.at(i) >> t.at(i);
    }
    int ans = INF;
    for(int i = 0; i < N; i++){
        if(t.at(i) <= T){
            if(ans > c.at(i)){
                ans = c.at(i);
            }
        }
    }
    if(ans == INF){
        cout << "TLE" << endl;
    }else{
        cout << ans << endl;
    }
}


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

// 型名の省略
typedef unsigned int uint;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> P;
typedef pair<lint, lint> Plint;
 
const int MOD = 1000000007;
const int INF = 1<<18;
const lint INFLINT = 1LL << 60;
const double PI=acos(-1.0);
 
// cinとcoutの高速化
#define endl "\n"
struct cinacc{cinacc(){cin.tie(0);ios::sync_with_stdio(false);}}cinaccc;
struct coutacc{coutacc(){cout.setf(ios::fixed);cout.precision(12);}}coutaccc;
 
// 繰り返し
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define reps(i,n) for(lint i=0;i<=(lint)(n);i++)
#define rrep(i,n) for(lint i=(lint)(n)-1;i>0;i--)
#define rreps(i,n) for(lint i=(lint)(n)-1;i>=0;i--)

#define pb push_back

#define ALL(s) (s.begin(), s.end())
#define SZ(s) (s.size())

template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T&a,const T&b){if(b<a){a=b;return true;}return false;}

// Union-Find-Tree
class UnionFind {
	vector<int> par;
	UnionFind(int n):par(n){rep(i,n)par[i]=i;}
	int root(int x){if(par[x]==x)return x;return par[x]=root(par[x]);}
	void unite(int x,int y){int rx=root(x);int ry=root(y);if(rx==ry)return;par[rx]=ry;}
	bool same(int x,int y){return root(x)==root(y);}
};

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;
    
    vector<vector<int>> to(n);
    rep(i, n - 1) {
        to[i].push_back(i + 1);
        to[i + 1].push_back(i);
    }
    to[x].push_back(y);
    to[y].push_back(x);
    
    vector<vector<int>> cost(n, vector<int>(n, INF));
    
    rep(i, n) {
        queue<int> q;
        q.push(i);
        cost[i][i] = 0;
        
        while(!q.empty()) {
            int now = q.front(); q.pop();
            for(int next : to[now]) {
                if(cost[i][next] == INF) {
                    cost[i][next] = cost[i][now] + 1;
                    q.push(next);
                }
            }
        }
    }
    
    vector<int> ans(n);
    rep(i, n) {
        for(int j = i + 1; j < n; j++) {
            ans[cost[i][j]]++;
        }
    }
    
    for(int i = 1; i < n; i++) {
        cout << ans[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 16128
#include <iostream>
#include <vector>
using namespace std;

vector<int> sieve(int n);

vector<int> sieve(int n){
    vector<int> primes(n);
    for(int i=2; i<n; i++){
        primes[i] = i;
    }
    for(int i=2; i*i<n; i++){
        if(primes[i]){
            for(int j=i*i; j<n; j+=i){
                primes[j] = 0;
            }
        }
    }
    return primes;
}

int main(){
    int n;
    vector<int> primes = sieve(10000);
    while(cin >> n){
        int cnt = 0;
        for(int i=2; i<=n; ++i) if(primes[i] != 0 & primes[n+1-i] != 0) ++cnt;
        cout << cnt << endl;
    }
    return 0;
}

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

int main(void){
    string s;
    while(true){
        cin>>s;
        if(cin.fail())break;
        for (int i = 0; i < 3; ++i) {
            if(s[0+3*i]==s[1+3*i]&&s[1+3*i]==s[2+3*i]&&s[2+3*i]=='o'){cout<<"o"<<endl;goto end;}
            if(s[0+3*i]==s[1+3*i]&&s[1+3*i]==s[2+3*i]&&s[2+3*i]=='x'){cout<<"x"<<endl;goto end;}
        }

        for (int i = 0; i < 3; ++i) {
            if(s[0+i]==s[3+i]&&s[3+i]==s[6+i]&&s[6+i]=='o'){cout<<"o"<<endl;goto end;}
            if(s[0+i]==s[3+i]&&s[3+i]==s[6+i]&&s[6+i]=='x'){cout<<"x"<<endl;goto end;}
        }
        for (int i = 0; i < 2; ++i) {
            if(s[0+2*i]==s[4]&&s[4]==s[8-2*i]&&s[4]=='o'){cout<<"o"<<endl;goto end;}
            if(s[0+2*i]==s[4]&&s[4]==s[8-2*i]&&s[4]=='x'){cout<<"x"<<endl;goto end;}
        }
        cout<<"d"<<endl;
        end:;
        if(s[9]==EOF)break;
    }
    return 0;
}


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

using namespace std;

int main()
{
    int N, k;
    ios::sync_with_stdio(0); cin.tie(NULL);
    cin >> N >> k;

    vector<int> H(N);
    vector<int> DP(N);

    for(int& x : H) cin >> x;
    DP[0] = 0;
    for(int i = 1; i < N; ++i) {
        DP[i] = 0x3f3f3f3f; 
        for(int prev = i - 1; i - prev <= k; --prev) {
            if( prev < 0) break;
            DP[i] = min( DP[i], DP[prev] + abs( H[prev] - H[i] ) );
        }
    }
    cout << DP[N - 1] << endl;
    return 0;    
}


Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const long long mod = 998244353LL;
const double pi = acos(-1.0);

double gosa = 0.00000001;

int main() {
	double a;
	while (cin >> a) {

		int ans = 0;
		for (int i = 0; true; i += 5) {
			double v = 9.8 * sqrt((double)i / 4.9);
			if (a-v < gosa) { ans = i; break; }
		}
		Cout((ans + 5) / 5);
	}
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;

signed main(){
    int N; cin>>N;
    map<string, vector<Pii>> M;
    string S; int P;
    REP(i,N){
        cin>>S>>P;
        M[S].pb(Pii(P,i));
    }
    for(auto p: M){
        vector<Pii> t = M[p.f];
        Sort(t); Reverse(t);
        REP(i,SZ(t)) Out(t[i].s+1);
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
long long int inf = 1e18;

int main() {

  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  map<int, int> mp;
  vector<int> tmp;
  for(int i=0; i<n; i++){
    cin >> a[i];
    if( mp.find(a[i]) == mp.end() ){
      tmp.push_back(a[i]);
    }
    mp[a[i]]++;
  }
  vector< pair<int, int> > c;
  for(int i=0; i<tmp.size(); i++){
    c.push_back({mp[tmp[i]], tmp[i]});
  }
  sort(c.begin(), c.end());
  int ans = 0;
  for(int i=0; i<max(0, (int)c.size()-k); i++){
    ans += c[i].first;
    cerr << c[i].first << " " << c[i].second << endl;
  }
  cout << ans << endl;
  return 0;
}




//


Measured memory_bytes: 13300