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

#define all(v) v.begin(),v.end()
#define rep(i,a,n) for(i=a;i<=n;i++)
#define f(i,n) for(i=0;i<n;i++)
#define fr first
#define sc second
#define pb emplace_back
#define pf push_front
#define mp make_pair
#define ll long long
#define endl "\n"
#define digit(n) floor(log10(n))+1
#define mod 1000000007
#define maxn 1000001
#define pow(a,b) (ll)(pow(a,b)+0.5)
#define inf 1e18
#define FASTIO std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//------------------- * Chaliye Shuru Karte Hain (code) * -------------------//
vector<ll> a(maxn),dp(maxn,-1);
ll minSteps(ll i,ll n){
    if(i==n)return 0;
    if(i>n)return inf;
    if(dp[i]!=-1)return dp[i];
    ll left=abs(a[i]-a[i+1])+minSteps(i+1,n);
    ll right=inf;
    if(i+2<=n){
        right=abs(a[i]-a[i+2])+minSteps(i+2,n);
    }
    return dp[i]=min(left,right);
}

int main()
{
    FASTIO
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll x=0,f=0,j,q=1,i,n,m,k;
    //cin>>q;
    while(q--)
    {
        cin>>n;
        rep(i,1,n)cin>>a[i];
        cout<<minSteps(1,n);
        cout<<endl;    
    }        
}

Measured memory_bytes: 23492
#include<iostream>
#include<cmath>
using namespace std;
#define MAXN 100000

int N;
int A[MAXN+1];

int main(){
  cin>>N;
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  A[0]=A[N+1]=0;
  int sum=0;
  for(int i=0;i<=N;i++){
    sum+=abs(A[i]-A[i+1]);
  }
  for(int i=1;i<=N;i++){
    int s=sum;
    s=s-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]);
    cout<<s<<endl;
  }
  return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    string s;
    cin >> s;
    int ans = 0;
    int n = s.size();
    rep(i, s.size()) {
        if (i%2==0 && s[i]=='0') ans++;
        if (i%2==1 && s[i]=='1') ans++; 
    }
    ans = min(ans, n-ans);
    
    cout << ans << endl;
    return 0;
}


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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};
fastio _fast_io;

ll a, b, n;
ll sum;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        sum += (i + 1) * (n - i);
    }
    for (int i = 0; i < n - 1; ++i) {
        cin >> a >> b; // [a, b]
        if (a > b)
            swap(a, b);
        sum -= a * (n - b + 1);
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3616
n = int(input())
p=list(map(int,input().split()))
a=0
b=0
f=0
for i in range(n):
    if p[i] == i +1:
        a+=1
        if f ==1 :
            b+=1
            f=0
        else:
            f=1
    else:
        f=0

print(a-b)


Measured memory_bytes: 14008
n = int(input())
w = list(map(int,input().split()))
r = w[0]
l = sum(w) - w[0]
ans = abs(r - l)
for i in range(1, len(w), 1):
  r += w[i]
  l -= w[i]
  if ans > abs(r - l):
    ans = abs(r- l)
print(ans)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int ans = 0;
		if (a < 10 && b < 10) {
			ans = a * b;
		} else {
			ans = -1;
		}
		System.out.println(ans);

	}

}


Measured memory_bytes: 23124
str=list(input())
flag=False
for i in range(len(str)):
    if(str[i]!='A' and str[i]!='C'):
        if(ord(str[i])>=ord('a') and ord(str[i])<=ord('z')):
            flag=True
        else:
            flag=False
            break
if(flag and str[0]=='A' and 'C' in str[2:len(str)-1:1] and str.count('C')==1):
    print("AC")
else:
    print("WA")
    

Measured memory_bytes: 3060
#include<iostream>
#include<limits.h>

#define N 100001
int n, k, k2;
int a[N], L[N], R[N];
int block[N];
int isW;

void sort(int l, int r){
	int i, j, t = l;
	int m = (l + r) / 2;
	if( l+1 >= r ){ return; }
	sort(l, m);
	sort(m, r);
	for( i = 0; i < m-l; i++ ){ L[i] = a[i+l]; }
	L[i] = INT_MAX;
	for( j = 0; j < r-m; j++ ){ R[j] = a[j+m]; }
	R[j] = INT_MAX;
	i = 0;
	j = 0;
	while( i < m-l || j < r-m ){
		if( L[i] < R[j] ){
			a[t++] = L[i++];
		}else{
			a[t++] = R[j++];
		}
	}
	return;
}

int input(){
	int i, t;
	std::cin >> n >> k;
	for( i = 0; i < k; i++ ){
		std::cin >> t;
		a[i-isW] = t;
		if( t == 0 ){ isW = 1; }
	}
	k2 = k-isW;
	sort(0, k2);
	return n;
}

int func(){
	int re = 0, m = 0, next = 0, i, j, t;
	block[m++] = -1;
	a[k2] = INT_MAX;
	for( i = 0; i < k2; i=next ){
		for( j = i; j < k2; j++ ){
			if( a[j+1] - a[j] != 1 ){ break; }
		}
		next = j+1;
		block[m++] = j;
	}
	for( i = 1; i < m-1; i++ ){
		if( isW && a[block[i]+1] - a[block[i]] == 2 ){
			t = a[block[i+1]] - a[block[i-1]+1] + 1;
		}else{
			t = a[block[i+1]] - a[block[i]+1] + 1;
		}
		if( t > re ){ re = t; }
	}
	return re;
}

int main(){
	while( input() > 0 ){ std::cout << func() << std::endl; }
	return 0;
}

Measured memory_bytes: 3700
A,B=map(int, input().split())

# 100 x 100 固定
print("100 100")

A -= 1
B -= 1
for y in range(50):
  s = ""
  if y%2 == 1:
    for x in range(100):
      if A > 0 and x%2 == 0:
        s += "."
        A -= 1
      else:
        s += "#"
    print(s)
  else:
    print("#" * 100)
for y in range(50):
  s = ""
  if y%2 == 1:
    for x in range(100):
      if B > 0 and x%2 == 0:
        s += "#"
        B -= 1
      else:
        s += "."
    print(s)
  else:
    print("." * 100)

Measured memory_bytes: 3064
# -*- coding:utf-8 -*-

def solve2():
    """解説PDF
    任意の偶数nについて n ^ (n+1) = 1

    この性質は、最下位ビットのみが異なることからわかる。

    たとえば、
    F(0, 6) = 0^1^2^3^4^5^6
            = (0^1)^(2^3)^(4^5)^6
            = 1^1^1^6
    のように計算できる。

    また、排他的論理和の性質として、

    a ^ b = c
    a = c ^ b

    が成り立つので、（両辺に ^b するイメージ。b^b=0 である）

    F(0, B) = F(0, A-1) ^ F(A, B)
    F(A, B) = F(0, A-1) ^ F(0, B)

    が成り立つ。
    """
    A, B = list(map(int, input().split()))

    def calc(a):
        """ F(0, a)を返す。計算量O(1) """
        if a == 0:
            return 0
        elif a == 1:
            return 1

        # aが2以上の時 
        if a%2 == 0:
            # aが偶数のとき
            # F(0, a) = 1^1^...^1^a
            # 1の数は a/2 個
            if (a/2)%2 == 0:
                _ans = a
            else:
                _ans = 1^a
        else:
            # aが奇数の時
            # F(0, a) = 1^1^...^1^1
            # 1の数は (a+1)/2 個
            if ((a+1)/2)%2 == 0:
                _ans = 0
            else:
                _ans = 1
        
        return _ans
    
    # F(A, B) = F(0, A-1) ^ F(0, B)
    ans = calc(A-1) ^ calc(B)
    print(ans)


def solve():
    A, B = list(map(int, input().split()))

    """解説
    考え方としては、累積和みたいなかんじ
    「4~8までのxor」は、「0~8までのxor」 から 「0~3までのxor」 を引くかんじ

    A xor B = C のとき、
    A xor C = B であることに着目する

    各桁の1の数を数えれば求まる

    ・1~8のxor
    0000 | 0
    0001 | 1
    0010 | 2
    0011 | 3
    0100 | 4
    0101 | 5
    0110 | 6
    0111 | 7
    1000 | 8
    ----
    1001

    ・各桁の01の周期に着目する
    ・0桁目の周期は2
    ・1桁目の周期は4
    ・2桁目の周期は8
    ・3桁目の周期は16
    """

    def calc(a):
        """ F(0, a)を返す。 計算量O(log(B))? """
        # 10**3 <= 2**10 は
        # 1000  <= 1024 なので
        # 10**12 <= 2**40 (2進数で40桁くらい)
        if a <= 0: return 0

        ans = 0
        for i in range(0, 50):
            # i桁目の周期Tを調べる
            # 0桁目 -> 周期T=2
            # 1桁目 -> 周期T=4
            # 2桁目 -> 周期T=8
            T = 1 << (i+1)

            # 各桁の1の個数は
            # cnt = (ループした回数) * (1が出てくる回数)
            cnt = ((a+1)//T) * (T/2)
            # cnt += あまった1の数を足す
            cnt += max(0, ((a+1)%T) - (T/2))

            # その桁の1の数が奇数だったら足し算する
            if cnt%2 == 1:
                ans += 1 << i
        
        return ans

    ans = calc(B) ^ calc(A-1)
    print(ans)

if __name__ == "__main__":
    solve2()


Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
constexpr double ep = 1e-9;

int main()
{
    double a, b, x, arg, ans;
    const double foo = 180.0 / acos(-1);
    cin >> a >> b >> x;
    if (x > (a * a * b / 2.0))
    {
        arg = 2.0 / a * (b - (x / a / a));
    }
    else
    {
        arg = a * b * b / x / 2.0;
    }
    ans = atan(arg);
    if (ans < ep)
    {
        cout << 0.0 << "\n";
        return 0;
    }
    cout << setprecision(12) << ans * foo << "\n";
    return 0;
}


Measured memory_bytes: 512
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  $a = array_map('intval', explode(" ", trim(fgets(STDIN))));
  $b=$a;

  rsort($a);

  $bunbo=$a[0];

  $bunshi=0;
  $sa=PHP_INT_MAX;
  for($i=1;$i<$n;$i++){
    if(abs($a[$i] - $bunbo / 2) < $sa){
      $bunshi = $a[$i];
      $sa = abs($a[$i] - $bunbo / 2);
    }
  }

  echo $bunbo." ".$bunshi;

Measured memory_bytes: 27064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 100011
#define mod 1000000007

const ll inf = (1LL << 60);

int n, m, i, S, T, u, v, d;
vector< pair<int, ll> > list[maxN];
pair<ll, ll> dist[2][maxN];
priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > H;

ll ans;

ll p2(ll x) {
    x %= mod;
    x *= x;
    x %= mod;
    return x;
}

void dijk(pair<ll, ll>* data, int S) {
    int i, j;

    for (i = 1; i <= n; i++) data[i] = mp(inf, 0);
    while (!H.empty()) H.pop();
    data[S] = mp(0, 1);
    H.push(mp(data[S].first, S));

    while (!H.empty()) {
        int node = H.top().second;
        ll dd = H.top().first;
        H.pop();

        if (data[node].first != dd) continue;

        for (auto to : list[node]) {
            if (data[to.first].first > data[node].first + to.second) {
                data[to.first].first = data[node].first + to.second;
                data[to.first].second = 0;
                H.push(mp(data[to.first].first, to.first));
            }

            if (data[to.first].first == data[node].first + to.second) {
                data[to.first].second += data[node].second;
                if (data[to.first].second >= mod) data[to.first].second -= mod;
            }
        }
    }
}

int main()
{
    //freopen("test.in","r",stdin);

    scanf("%d%d%d%d", &n, &m, &S, &T);
    for (i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &d);
        list[u].pb(mp(v, d));
        list[v].pb(mp(u, d));
    }

    dijk(dist[0], S);
    dijk(dist[1], T);

    ans = p2(dist[0][T].second);
    for (i = 1; i <= n; i++) {
        if (dist[0][i].first + dist[1][i].first == dist[0][T].first) {
            if (dist[0][i].first == dist[1][i].first) {
                ans += mod - p2(1LL * dist[0][i].second * dist[1][i].second);
                if (ans >= mod) ans -= mod;
            }
        }

        for (auto to : list[i]) {
            if (dist[0][i].first + to.second + dist[1][to.first].first == dist[0][T].first) {
                if (2LL * dist[0][i].first < dist[0][T].first &&
                    2LL * (dist[0][i].first + to.second) > dist[0][T].first) {

                    ans += mod - p2(1LL * dist[0][i].second * dist[1][to.first].second);
                    if (ans >= mod) ans -= mod;
                }
            }
        }
    }

    printf("%lld", ans);

    return 0;
}


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

using namespace std;

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

void solve()
{
	int p, q, r;
	cin >> p >> q >> r;
	cout << min(p, q) + min(max(p, q), r) << "\n";
	
}

int main()
{
	solve();
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
from collections import Counter

n, m = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cnt_t = [0] * m

ans = [0] * m
cnt_r = [0] * (m + 1)
for a1, a2 in zip(a, a[1:]):
    ans[0] += min((m + a2 - a1) % m, (m + a2 - 0) % m + 1)
    cnt_t[a2] += (m + a2 - a1) % m - 1
    if (m + a2 - a1) % m <= 1:
        continue
    add = (a1 + 2) % m
    sub = a2 + 1
    if add < sub:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
    else:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
        cnt_r[0] += 1
        cnt_r[m] -=1
for i in range(m):
    cnt_r[i+1] += cnt_r[i]

for i in range(1, m):
    ans[i] = ans[i - 1] - cnt_r[i] + cnt_t[i - 1]
print(min(ans))

Measured memory_bytes: 54288
#include<iostream>
using namespace std;
int main(){
    int n,x;
    int card[5][14];
    cin>>n;
    char a;
    
    for(int i=1;i<=4;i++){
        for(int j=1;j<=13;j++){
            card[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>a>>x;
        if(a=='S'){
            card[1][x]=1;
        }
        else if(a=='H'){
            card[2][x]=1;
        }
        else if(a=='C'){
            card[3][x]=1;
        }
        else if(a=='D'){
            card[4][x]=1;
        }
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=13;j++){
            if(card[i][j]!=1){
                if(i==1){
                    cout<<'S'<<" "<<j<<endl;
                }
                else if(i==2){
                    cout<<'H'<<" "<<j<<endl;
                }
                else if(i==3){
                    cout<<'C'<<" "<<j<<endl;
                }
                else if(i==4){
                    cout<<'D'<<" "<<j<<endl;
                }
            }
        }
    }
    
    return 0;
}


Measured memory_bytes: 3084
#include <iostream>
#include <stdlib.h>
using namespace std;

int cmp(const void *a,const void *b){
	return *(int*)a-*(int*)b;
}

int main(){
	int N,K,min=-1;cin>>N>>K;
	int h[100000];
	for(int i=0; i<N; i++)
		cin>>h[i];
	qsort(h,N,sizeof(int),cmp);
	for(int i=0; i+K-1<N; i++){
		if(min>h[i+K-1]-h[i]||min==-1)
			min=h[i+K-1]-h[i];
	}
	cout<<min;
    return 0;
}

Measured memory_bytes: 1020
#include <cstdio>
using namespace std;

int min(int a, int b) {
	if (a <= b)return a;
	return b;
}

int main() {
	int A, B, C, D, P;
	int sum1, sum2;

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

	sum1 = A*P;
	sum2 = B + ((P > C) ? D*(P - C) : 0);

	printf("%d\n", min(sum1, sum2));

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int n,k;
	int *p;
	cin >> n >> k;
	p = new int[n];
	for(int i = 0;i < n;i++){
		cin >> p[i];
	}
	sort(p,p+n);
	int sum=0;
	for(int i = 0;i < k;i++){
		sum += p[i];
	}
	cout << sum;
	return 0;
}


Measured memory_bytes: 3640
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
A = [AB[i][0] for i in range(N)]
B = [AB[i][1] for i in range(N)]
dp = [10**9]*(2*10**4+1)
dp[0] = 0
for h in range(10**4+1):
    for i in range(N):
        dp[h+A[i]] = min(dp[h+A[i]],dp[h]+B[i])


ans = 10**9
for i in range(H,2*10**4+1):
    ans = min(ans,dp[i])

print(ans)

Measured memory_bytes: 43100
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    string S;

    cin >> N;

    int AC = 0;
    int WA = 0;
    int TLE = 0;
    int RE = 0;

    for (int i = 0; i < N; ++i)
    {
        cin >> S;

        if (S == "AC")
        {
            AC = AC + 1;
        }

        if (S == "WA")
        {
            WA = WA + 1;
        }

        if (S == "TLE")
        {
            TLE = TLE + 1;
        }

        if (S == "RE")
        {
            RE = RE + 1;
        }
    }

    cout << "AC x " << AC << endl;
    cout << "WA x " << WA << endl;
    cout << "TLE x " << TLE << endl;
    cout << "RE x " << RE << endl;
}

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

ll N;
ll A[100005];
ll solve(ll p){
  ll res = 0;
  ll sum = 0;
  for(ll i=0;i<N;i++) {
    ll a = A[i];
    sum += a;
  //  cout << a << " "<< sum << endl;
    if ((i+p) & 1) { // -
      if (sum < 0) continue;
      res += abs((-1 - sum));
      sum = -1;
    } else { // +
      if (sum > 0) continue;
      res += abs((1 - sum));
      sum = 1;
    }
//    cout << "change -> " << sum << " " <<res<< endl;
  }
  return res;
}


int main(){
  cin >> N;
  for(ll i=0;i<N;i++) {
    cin >> A[i];
  }
  cout << min( solve(0), solve(1) ) << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define MOD 1000000007

using namespace std;
int n,m;

int gridPath(vector<vector<char> >g){
    vector<vector<int> > dp(n+1, vector<int>(m+1,0));
    dp[0][1] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i-1][j-1]=='#')
                dp[i][j] = 0;
            else
                dp[i][j] = (dp[i-1][j]+dp[i][j-1])%MOD;
        }
    }
    return dp[n][m];
}

int main(){
    cin>>n>>m;
    vector<vector<char> > g(n, vector<char>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cout<<g[i][j]<<" ";
        cout<<endl;
    }*/
    cout<<gridPath(g)<<endl;
    return 0;
}


Measured memory_bytes: 9220
import scala.io.StdIn.{readInt, readLine}

object Main extends App {
  var Array(p1, p2) = Array(0, 0)
  val m = readInt()
  for (_ <- 1 to m) {
    val Array(c1, c2) = readLine().split(" ")
    if (c1 > c2) p1 += 3
    else if (c2 > c1) p2 += 3
    else { p1 += 1; p2 += 1 }
  }
  println(s"$p1 $p2")
}



Measured memory_bytes: 45056
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
	char a[200];
	scanf("%s", a);
	int p = 0, q = 0;
	for (int i = 0; a[i] != '\0'; ++i)
	{
		if (!p && a[i] == 'C') p = 1;
		else if (p && !q && a[i] == 'F') q = 1;
	}
	if (p && q) puts("Yes");
	else puts("No");
	return 0;
} 

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

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

  vector<int> p(N);
  for(int i = 0; i < N; i++){
    cin >> p[i];
  }
  
  long long e_now_2 = 0; // 2 * expected value
  for(int i = 0; i < K; i++){
    e_now_2 += p[i] + 1;
  }

  long long ans_2 = e_now_2;
  for(int j = K; j < N; j++){
    e_now_2 -= p[j - K] + 1;
    e_now_2 += p[j] + 1;
    ans_2 = max(ans_2, e_now_2);
  }

  cout << setprecision(10);
  cout << ans_2 / 2.0 << endl;
}

  


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 1; i < (int)(n); i++)
typedef long long ll;

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

int dp[100];

//最大公約数
int gcd(int x, int y){
  if(x % y == 0) return y;
  return gcd(y, x % y);
}
//最小公倍数
int lcm(int x, int y){
  return x * y / gcd(x, y);
}
//フィボナッチ数列
//配列dpを-1で初期化する
int fib(int n){
  if(n == 0 || n == 1) return dp[n] = 1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n - 1) + fib(n - 2);
}
//階乗計算(factorial)
int fact(int n){
  if(n = 1) return 1;
  return n * fact(n - 1);
}
//累乗計算(Exponentiation)
//x**y
ll expo(int x, int y){
  ll ans = 1;
  rep(i, y){
    ans *= x;
  }
  return ans;
}
//桁数
int keta(ll x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    x /= 10;
    res++;
  }
  return res;
}


int main(){
  while(1){
    int h, w;
    cin >> h >> w;
    if(h == 0 && w == 0) return 0;

    rep(i, h){
      rep(j, w){
        if(i != 0 && i != h-1 && j != 0 && j != w-1){
          cout << '.';
        }
        else{
          cout << '#';
        }
      }
      cout << endl;
    }
    cout << endl;
  }
}






Measured memory_bytes: 3096
N,M,Q = gets.chomp.split.map(&:to_i)
a,b,c,d = Q.times.map{gets.chomp.split.map(&:to_i)}.transpose
An = (1..M).to_a.repeated_combination(N).to_a
ans = 0

An.each do |i|
  point = 0
  (0..Q-1).each do |j|
    if i[b[j]-1] - i[a[j]-1] == c[j]
      point += d[j]
    end
  end
  ans = point if ans <= point
end

puts ans

Measured memory_bytes: 32516
#include <stdio.h>
#include <sysexits.h>
#include <math.h>

int main(void){
  int b,i,j;
  char S[4];
  int a[4];
  if(scanf("%s",&S)!=1){
   exit(0);
  }
  b=0;
  //printf("S=%s",S);
  for(i=0;i<3;i++){
    for(j=i+1;j<4;j++){
      if(S[i]==S[j]){
	b=b+1;
     }
    }
  }
  if(b==2){
  printf("Yes");
  }
  else{
    printf("No");
  }
  return 0;
}


Measured memory_bytes: 128
using System;
class Program
 {
        static void Main(string[] args)
        {
     　　int N, K;
         string[] str = Console.ReadLine().Split(' ');
         N = int.Parse(str[0]);
         K = int.Parse(str[1]);
         Console.WriteLine(N%K>0?1:0);
        }
 }

Measured memory_bytes: 13140
import java.util.*;

public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        Integer numMonster = sc.nextInt();
        Integer numHissatsu = sc.nextInt();
        sc.nextLine();
        
        int count = 0;
        long[] hpLine = new long[numMonster];
        while (sc.hasNext()) {
            long j = sc.nextInt();
            hpLine[count] = j;
            count++;
        }
        
        sc.close();
        
        Arrays.sort(hpLine);
        
        long cnt = 0;
        Integer startInt = numMonster - numHissatsu - 1;
        
        for(int i = startInt; i >= 0; i--) {
            cnt = cnt + hpLine[i];
        }
        
        System.out.println(cnt);
    }
}


Measured memory_bytes: 95648
#include <iostream>
#include <vector>

using namespace std;

int main(){
    vector<int> a(3);
    vector<int> b(3);
    vector<vector<int>> c(3,vector<int>(3));
    for (int i = 0; i <3 ; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> c[i][j];
        }
    }

    for (a[0] = 0; a[0] < 101 ; ++a[0]) {
        for (a[1] = 0; a[1] < 101; ++a[1]) {
            for (a[2] = 0; a[2] < 101; ++a[2]) {
                b[0] = c[0][0] - a[0];
                b[1] = c[1][1] -a[1];
                b[2] = c[2][2] -a[2];
                int f = 0;
                for (int i = 0; i <3 ; ++i) {
                    for (int j = 0; j < 3; ++j) {
                        if (c[i][j] == a[i] + b[j]){
                            f++;
                        }
                    }
                }

                if(f == 9){
                    cout << "Yes";
                    return 0;
                }
            }
        }
    }

    cout << "No";
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	int a,b;
	scanf("%d %d",&a,&b);
	a=n*a;
	a=min(a,b);
	printf("%d\n",a);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#define N_MAX 100000
int n, m, k, i, x[N_MAX + 1], ans;
int main()
{
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; ++i)
		scanf("%d", &x[i]);
	if (x[1] >= 0)
		printf("%d\n", x[m]);
	else if (x[n] <= 0)
		printf("%d\n", -x[n - m + 1]);
	else
	{
		ans = 0x3F3F3F3F;
		for (k = 1; k < n && x[k] < 0; ++k);
		if (k + m - 1 <= n)
			ans = std::min(ans, x[k + m - 1]);
		for (i = std::max(k, m); i <= std::min(n, k + m - 2); ++i)
			ans = std::min(ans, x[i] * 2 - x[i - m + 1]);
		for (; k > 1 && x[k] > 0; --k);
		if (k >= m)
			ans = std::min(ans, -x[k - m + 1]);
		for (i = std::min(k, n - m + 1); i >= std::max(1, k - m + 1); --i)
			ans = std::min(ans, x[i + m - 1] - x[i] * 2);
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(){

  int in[5], out[5];

  while(1){

    cin >> in[0] >> out[0];

    if(in[0] == 0 && out[0] == 0) break;

    for(int i = 1; i < 5; i++){
      in[i] = in[0] % 10;
      in[0] /= 10;
      out[i] = out[0] % 10;
      out[0] /= 10;
    }

    int hit = 0, blow = 0;

    for(int i = 1; i < 5; i++){
      if(in[i] == out[i]) hit++;
    }

    for(int i = 1; i < 5; i++){
      for(int j = 1; j < 5; j++){
	if(in[i] == out[j]) blow++;
      }
    }

    blow -= hit;

    cout << hit << " " << blow << endl;

  }

  return 0;
}

Measured memory_bytes: 864
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
int dy[]={1,-1,0,0};
int dx[]={0,0,1,-1};


int main(){
  int N,M;
  cin>>N>>M;
  vector<pair<int,int>> war(M);

  int b,a;
  for(int i=0;i<M;i++){
    cin>>a>>b;
    war[i]={b,a};
  }

  sort(war.begin(),war.end());
  int pos=-1;
  int ans=0;
  for(int i=0;i<M;i++){
    if(war[i].second>=pos){
      ans++;
      pos=war[i].first;
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <math.h>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;

using namespace std;

ll M[100005];
ll T[100005];
ll A[100005];

int main()
{
	int N;
	cin >> N;
	REP(i, N)
	{
		cin >> T[i];
	}
	REP(i, N)
	{
		cin >> A[i];
	}

	REP(i, N)
	{
		M[i] = 1;
		if (i > 0 && T[i] == T[i - 1])
		{
			M[i] = T[i];
		}
	}

	IREP(i, N - 1)
	{
		if (M[i] == 1 && T[i] > A[i])
		{
			M[i] = 0;
			continue;
		}
		if (i < N - 1 && A[i] == A[i + 1])
		{
			M[i] = std::min(M[i], A[i]);
		}
		else if (T[i] < A[i])
		{
			M[i] = 0;
		}
		else
		{
			M[i] = 1;
		}
	}

	ll ans = 1;
	REP(i, N)
	{
		ans *= M[i];
		ans %= MOD;
	}

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

Measured memory_bytes: 2560
#include<stdio.h>
int main()
{
	int n,jyouhou[1000][4]={0},i,p,q,r,P,Q,R,C,x,a=0,CL,ari=0;
	while(scanf("%d",&n)&&n!=0)
	{
		for(x=0; x<n; x++)
		{
			scanf("%d %d %d %d",&i,&p,&q,&r);
			jyouhou[a][0]=i;
			jyouhou[a][1]=p;
			jyouhou[a][2]=q;
			jyouhou[a][3]=r;
			a++;
		}
		scanf("%d %d %d %d",&P,&Q,&R,&C);
		a=0;
		for(x=0; x<n; x++)
		{
			if(jyouhou[a][1]<=P)
			{
				if(jyouhou[a][2]<=Q)
				{
					if(jyouhou[a][3]<=R)
					{
						CL=jyouhou[a][1]*4+jyouhou[a][3]*4+jyouhou[a][2]*9;
						if(CL<=C)
						{
							ari=1;
							printf("%d\n",jyouhou[a][0]);
						}
					}
				}
			}
			a++;
		}
		if(ari==0)
			printf("NA\n");
		a=0;
		ari=0;
	}
	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair< int, int >;

int main() {
    int K;
    cin >> K;
    if (K <= 9) {
        cout << K << endl;
        return 0;
    }
    ll n = 0LL;
    int cnt = 0;
    queue< ll > que;
    for (ll i = 1LL; i <= 9LL; ++i) que.push(i);
    while (true) {
        n = que.front();
        que.pop();
        ++cnt;
        if (cnt == K) break;
        ll r = n % 10LL;
        if (r == 0LL) {
            que.push(n * 10LL + r);
            que.push(n * 10LL + r + 1LL);
        }
        if (r != 0LL && r != 9LL) {
            que.push(n * 10LL + r - 1LL);
            que.push(n * 10LL + r);
            que.push(n * 10LL + r + 1LL);
        }
        if (r == 9LL) {
            que.push(n * 10LL + r - 1LL);
            que.push(n * 10LL + r);
        }
    }
    cout << n << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
vector <int> adj[100005];
int *v;

int longpath(int root)
{
    if (v[root]!=-1)
        return v[root];
    
    if (adj[root].empty())
    {
        v[root] = 0;
        return 0;
    }
    
    int edgemax = -100;
    for (int i = 0; i<adj[root].size(); i++)
    {
        edgemax = max(edgemax, 1+longpath(adj[root][i]));
    }
    v[root] = edgemax;
    return v[root];
}

int main()
{
    int n, m;
    cin>>n>>m;
    
    v = new int[n+5];
    for (int i = 0; i<=n; i++)
        v[i] = -1;
    
    for (int i = 0; i<m; i++)
    {
        int x, y;
        cin>>x>>y;
        adj[x].push_back(y);
    }
    int maxm = 0;
    for (int i = 1; i<=n; i++)
    {
        v[i] = longpath(i);
        maxm = max(maxm, v[i]);
    }
    
    cout<<maxm;
    return 0;
}


Measured memory_bytes: 8192
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val result = mutableSetOf<Int>()

    for (i in N downTo 1) {
        //i自身を除くiの倍数の箱のボールの総数を求める
        var j = i * 2
        var t = 0
        while (j <= N) {
            if (result.contains(j)) t++
            j += i
        }

        //上で求めた値とa_iの値が異なる場合iの箱にボールを入れる
        if (t % 2 != a[i - 1]) result.add(i)
    }
    println(result.size)
    println(result.joinToString(separator = " "))
}

Measured memory_bytes: 97220
n = int(input())

def calc(x_list):
    tmp  = []
    for x in x_list:
        m = max(x)
        for alpha in range(ord('a'), ord(m) + 2):
            tmp.append(x + chr(alpha))
    if len(tmp[-1]) < n:
        tmp = calc(tmp)
    return tmp

ans = calc(['a'])
ans.sort()
if n >= 2:
    print(*ans, sep="\n")
else:
    print('a')

Measured memory_bytes: 19572
#include <bits/stdc++.h>
#include <algorithm>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ll long long 
#define pb push_back
#define mk make_pair
#define mod 1e9+7
using namespace std;

ll gcd(ll a, ll b){
    return __gcd(a,b);
}

ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}

bool isPrime(ll n){
    if(n <= 1) return false;
    for(ll i=2; i<=sqrt(n); i++){
        if(n%i == 0){
            return false;
        }
    }
    return true;
}

void solve(){
    ll n;
    cin >> n;
    cout << (n+pow(n,2)+pow(n,3)) << endl;
}

int main() {
    fast;
    solve();
	//ll t; cin >> t; while(t--){ solve(); }
	return 0;
}

Measured memory_bytes: 4160
#include <iostream>
#include <set>
using namespace std;

int main() {
	int A, B, K;
	cin >> A >> B >> K;
	set<int> s;
	for (int i = 0; i < K; i++) {
		if (i > (B - A)) break;
		s.insert(A + i);
		s.insert(B - i);
	}

	for (auto x : s) {
		cout << x << endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int m[1000050];
int main(){
	
	int n,fs,lr,defm;
	cin>>n>>fs>>lr;
	
	for(int i=1;i<=n;i++){
		m[i]=fs;
	}
	
	for(int i=1;i<=lr;i++){
		cin>>defm;
		m[defm]+=1;
	}
	
	//printf("%d",m[3]);
	
	for(int i=1;i<=n;i++){
		if(m[i]-lr>0){
			printf("Yes");
		}else{
			printf("No");
		}
		printf("\n");
	}
	
	return 0;
}


//4 4 3 5 3 3






Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<n;i++)
int main(void){
    // Your code here!
    vector<string> YN{"NO","YES"};
    vector<string> yn{"No","Yes"};
    int a,b,c;
    cin>>a;
    cout<<yn[a/10==9||a%10==9]<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define mod (int)(1e9 + 7)

typedef struct {
	long long int s;
	long long int l;
}pair;

int min(int a, int b){
	if(a < b){
		return a;
	}
	else{
		return b;
	}
}

pair inverse_sub(int a, int b){
	pair h;
	if(a == 1){
		h.s = 1;
		h.l = 0;
		return h;
	}
	else{
		pair g = inverse_sub(b % a, a);
		h.s = g.l - (b / a) * g.s;
		h.l = g.s;
		return h;
	}
}

long long int inverse(int a, int p){
	int ans = inverse_sub(a, p).s;
	if(ans >= 0){
		return ans % p;
	}
	else{
		return p + ans % p;
	}
}
/*
//入力値が大きいとスタック領域が足りない
long long int combination(int n, int k){
	if(k == 0){
		return 1;
	}
	else{
		return (combination(n - 1, k - 1) * ((n * inverse(k, mod)) % mod)) % mod;
	}
}
*/

long long int combination(int n, int k){
	int i;
	long long int *comb = (long long int *)malloc(sizeof(long long int) * (k + 1));
	comb[0] = 1;
	for(i = 1; i <= k; i++){
		comb[i] = (comb[i - 1] * (((n - k + i) * inverse(i, mod)) % mod)) % mod;
	}
	long long int ans = comb[k];
	free(comb);
	return ans;
}


int main(){
	int H, W, A, B, i;
	scanf("%d%d%d%d", &H, &W, &A, &B);
	long long int ways, sum;
	ways = combination(W - B + H - 2, min(W - B - 1, H - 1));
	sum = ways;
	for(i = 1; i <= H - A - 1; i++){
		ways = (((((ways * (B - 1 + i)) % mod) * (H - i)) % mod) * ((inverse(i, mod) * inverse(W - B - 1 + H - i, mod)) % mod)) % mod;
		sum = (sum + ways) % mod;
	}
	printf("%lld\n", sum);
	return 0;
}

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

 int main(){
    int n,cou=0;
    cin >> n ;
    vector<int> a(n);
    vector<int> p(n);
    for(int i=0;i<n;i++){
       cin >> a.at(i);
       p.at(i)=a.at(i);
    }
    sort(p.begin(),p.end());
    for(int i=0;i<n;i++){
       if(p.at(i)!=a.at(i)){
          cou++;
       }
    }

    if(cou<=2){cout << "YES" << endl;}
    else{cout << "NO" << endl;}
    
 }

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

#define int long long
#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define reps(i, n) for (int (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for (int (i) = (n - 1); (i) >= 0; (i)--)
#define rreps(i, n) for (int (i) = (n); (i) > 0; (i)--)
typedef vector<int> vint;
typedef pair<int, int> pint;
const double PI = 3.141592653589793238462643383279;
const int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> inline bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
struct Init {
    Init() {
        cout << fixed << setprecision(20);
    };
} init;

int N, L;
int a[110000];
signed main() {
    cin >> N >> L;
    reps(i, N) { cin >> a[i]; }
    reps(i, N - 1) {
        if (a[i] + a[i + 1] < L) { continue; }
        cout << "Possible" << endl;
        reps(j, i - 1) { cout << j << endl; }
        for (int j = N - 1; j > i; j--) { cout << j << endl; }
        cout << i << endl;
        return 0;
    }
    cout << "Impossible" << endl;
}

Measured memory_bytes: 1664
while True:
    try:
        n = int(input())
    except:
        break

    if n == 0: break

    char = []
    name = []
    times = []

    scores = {i: n + 1 for i in range(30)}

    for i in range(n):
        char = input().split()

        name.append(char[0])
        times.append(list(map(int, char[2:])))

        for t in times[i]:
            scores[t] = scores[t] - 1

    res = {}
    for i in range(n):
        res[i] = sum([scores[t] for t in times[i]])

    score = min(res.values())

    names = [name[i] for i in range(n) if score == res[i]]
    names.sort()
    print(score, names[0])

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

int N;
int A[11];
int ans = 0;
using Int = long long;
void dfs(int i, Int S) {
    // cout << i << ", " << S << endl;
    if (i == N) {
        ans += S % 2 == 0;
        return;
    }
    dfs(i + 1, S * (A[i] - 1));
    dfs(i + 1, S * (A[i]));
    dfs(i + 1, S * (A[i] + 1));
}
int main() {
    cin >> N;
    rep(i, N) cin >> A[i];

    dfs(0, 1);
    cout << (ans) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>

#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())

#define fs first
#define sc second

using namespace std;

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

int main()
{
  ll N;

  cin >> N;

  P arr[N];

  ll parity;
  for (int i = 0; i < N; i++)
  {
    ll a, b;
    cin >> a >> b;
    arr[i] = P(a, b);
    if (i == 0)
    {
      parity = abs((a + b) % 2);
    }
    else
    {
      if(parity != abs((a + b)%2))
      {
        cout << -1 << endl;
        return 0;
      }
    }
  }

  ll narm = 39;
  if (parity == 0)
  {
    cout << narm + 1 << endl;
    cout << 1 << " ";
  }
  else 
    cout << narm << endl;

  for (ll j = narm-1; j >= 0; j--)
  {
    cout << (1LL << j);
    if(j > 0)
      cout << " ";
  }
  cout << endl;

  for (int i = 0; i < N; i++)
  {
    string ans;
    ll tmpx = arr[i].first;
    ll tmpy = arr[i].second;
    if(parity == 0)
     tmpx--;
    for (ll j = narm - 1; j >= 0; j--)
    {
      if (abs(tmpx) > abs(tmpy))
      {
        if(tmpx >= 0)
        {
          tmpx = tmpx - (1LL << j);
          ans += "R";
        }
        else
        {
          tmpx = (1LL << j) + tmpx;
          ans += "L";          
        }
      }
      else
      {
        if (tmpy >= 0)
        {
          tmpy = tmpy - (1LL << j);
          ans += "U";
        }
        else
        {
          tmpy = (1LL << j) + tmpy;
          ans += "D";
        }
      }
    } // j
    if(parity == 0)
      cout << "R";
    cout << ans << endl;
  } // i

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fst first
#define sec second
#define ULTRA 2134567890
#define de(x) if(x!=0 && MODE==x)
#define MODE 1
using namespace std;

int N,M;
vector<int> adj[100007] = {};
int dp[100007] = {};
int ans[100007] = {};
vector<int> pre[100007] = {};
vector<int> suf[100007] = {};

void dfs(int x, int p) {

    dp[x] = 1;
    for (auto y: adj[x]) {
        if (y == p)
            continue;
        dfs(y, x);
        dp[x] *= dp[y] + 1;
        dp[x] %= M;
    }

    int sz = adj[x].size();
    if (sz > 1) {
        pre[x].resize(sz);
        if (adj[x][0] != p)
            pre[x][0] = (dp[ adj[x][0] ] + 1) % M;
        else
            pre[x][0] = 1;
        for (int i=1; i<sz; i++) {
            if (adj[x][i] != p)
                pre[x][i] = pre[x][i-1] * (dp[ adj[x][i] ]+1) % M;
            else
                pre[x][i] = pre[x][i-1];
        }
        suf[x].resize(sz);
        if (adj[x][sz-1] != p)
            suf[x][sz-1] = (dp[ adj[x][sz-1] ] + 1) % M;
        else
            suf[x][sz-1] = 1;
        for (int i=sz-2; i>=0; i--) {
            if (adj[x][i] != p)
                suf[x][i] = suf[x][i+1] * (dp[ adj[x][i] ]+1) % M;
            else
                suf[x][i] = suf[x][i+1];
        }
    }
}

void dfs2(int x, int p) {
    ans[x] = dp[x];
    int sz = adj[x].size();
    for (int i=0; i<sz; i++) {
        int y = adj[x][i];
        if (y == p)
            continue;
        dp[x] = 1;
        dp[x] *= (i>0 ? pre[x][i-1] : 1);
        dp[x] %= M;
        dp[x] *= (i<sz-1 ? suf[x][i+1] : 1);
        dp[x] %= M;
        dp[x] *= (x==p ? 1 : dp[p]+1);
        dp[x] %= M;
        // printf("dp[%lld] = %lld\n", x, dp[x]);
        int tmp = dp[y];
        dp[y] *= dp[x] + 1;
        dp[y] %= M;
        dfs2(y, x);
        dp[y] = tmp;
    }
    dp[x] = ans[x];
}

main() {
    int i,j;

    cin >> N >> M;
    for (i=1; i<=N-1; i++) {
        int x1, x2;
        cin >> x1 >> x2;
        adj[x1].push_back(x2);
        adj[x2].push_back(x1);
    }

    dfs(1, 1);
    dfs2(1, 1);
    for (i=1; i<=N; i++)
        printf("%lld\n", ans[i]);

    return 0;
}

//
//          ___ ___  __________  __________
//         /////\  \/\   ______\/\\\\\\\\\\\  Code by ~Ice Tea~ of
//        //// \ \  \ \  \_____/\ \\\\_____/      New Empire of CHSH ...
//       ////   \ \  \ \  \      \ \\\\\\\\\\\
//      ////__   \ \  \ \  \      \ \\\\_____/
//     ///////\   \ \  \ \  \______\ \\\\_______   ________
//    ////____/    \ \__\ \___   ___\ \\\\\\\\\\\ _\  ___  \_
//   /__/           \/__/\/__/\  \__/\ \\\\_____//\  .\_/\_  \
//                           \ \  \   \ \\\\\\\\\\\\  \_\/_\  \
// ... with the AC Power of   \ \  \   \ \\\\_____/ \   _____  \
//   The Great Tsundere Doggy. \ \  \   \ \\\\     \ \  \  \ \  \
//                              \ \__\   \ \\\\\\\\\\ \__\  \ \__\
//                               \/__/    \/________/\/__/   \/__/
//


Measured memory_bytes: 27692
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

lli body(lli a, lli b){
	return (a-b)*(a-b);
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	lli n, a, b, ans;
	cin >> n >> a >> b;
	if(b < a || (n == 1 && a != b)) ans = 0;
	else if(n == 1 && a == b) ans = 1;
	else ans = (n-2)*(b-a) + 1;

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


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

#define V 10000
#define M 2000000

int main(){
    unsigned short *a, *b;
    
    int c[V+ 1],n, i, j;
    
    scanf("%d",&n);
    
    a=malloc(sizeof(short) * n+1);
    b=malloc(sizeof(short) * n+1);
    
    for (i=0;i<=V;i++)c[i]=0;
    
    for(i=0;i<n;i++){
        scanf("%hu",&a[i+1]);
        c[a[i+1]]++;
    }
    
    for(i=1;i<=V;i++)c[i]=c[i]+c[i-1];
    
    for(j=1;j<=n;j++){
        b[c[a[j]]]=a[j];
        c[a[j]]--;
    }
    
    for(i=1;i<=n;i++){
        if(i>1)printf(" ");
        printf("%d",b[i]);
    }
    printf("\n");
    
    return 0;
}




Measured memory_bytes: 9596
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
int h, w, ar[15];
bool used[15], ev;
char s[12][12];
inline bool isRev(char a[], char b[]){
	rep(i,h) if(a[i] != b[h-1-i]) return false;
	return true;
}
bool dfs(int p, int n, int e){
	if(e){
		rep(i,h){
			used[i] = true; ar[h/2] = i;
			if(dfs(0,0,0)) return true;
			used[i] = false;
		}
		return false;
	}else if(n != h/2){
		while(used[p]) p++;
		for(int i = p+1; i < h; i++) if(!used[i]){
			used[i] = true;
			ar[n] = p; ar[h-1-n] = i;
			if(dfs(p+1, n+1, 0)) return true;
			used[i] = false;
		}
		return false;
	}else{
		char temp[15][15];
		bool u[15] = {}, ev = !(w%2);
		rep(i,w) rep(j,h) temp[i][j] = s[ar[j]][i];
		rep(i,w){
			for(int j = i+1; j < w && !u[i]; j++) if(!u[j])
				u[i] = u[j] = isRev(temp[i], temp[j]);
			if(!u[i] && !ev) u[i] = ev = isRev(temp[i], temp[i]);
			if(!u[i]) return false;
		}
		return true;
	}
}
int main(){
	scanf("%d%d", &h, &w);
	rep(i,h) scanf("%s", s[i]);
	puts(dfs(0,0,h%2) ? "YES" : "NO");
}

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

int main(){
    int N; cin >> N;
    string s; cin >> s;
    int A[N], f[N], r[N];
    
    int tmp = 0;
    for(int i = 0; i < N; i++){
        if(s[i] == 'W') tmp++;
        f[i] = tmp;
    }
    tmp = 0;
    for(int i = N-1; i >= 0; i--){
        if(s[i] == 'E') tmp++;
        r[i] = tmp;
    }
    A[0] = r[1];
    A[N-1] = f[N-2];

    for(int i = 1; i < N-1; i++){
        A[i] = f[i-1] + r[i+1];
    }
    int ans = *min_element(A, A+N);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4228
#include <stdio.h>
#define A 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n , m[A][A];

int color[A] , d[A] , f[A] , tt;

void dfs(int u)
{
	int v ;
	color[u] = GRAY;
	d[u] = ++tt;
	for(v = 0; v < n; v++)
	{
		if(m[u][v] == 0)
		{
			continue;
		}
		if(color[v] == WHITE)
		{
			dfs(v);
		}
	}
	color[u] = BLACK;
	f[u] = ++tt;
}

void df()
{
	int u;
	for(u = 0; u < n; u++)
	{
		color[u] = WHITE;
		
	}
	tt = 0; 
	for( u = 0; u < n; u++)
	{
		if(color[u] == WHITE)
		{
			dfs(u);
		}
	}
	for(u = 0; u < n; u++)
	{
		printf("%d %d %d\n",u+1,d[u],f[u]);
	}
}

int main(void)
{
	int u, v , k, i,j;
	scanf("%d",&n);
	
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			m[i][j] = 0;
		}
	}
	for(i = 0; i < n; i++)
	{
		scanf("%d %d",&u,&k);
		u--;
		for(j = 0; j < k; j++)
		{
			scanf("%d",&v);
			v--;
			m[u][v] = 1;
		}
	}
	df();
	return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define fastio()                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define pb push_back
#define show(x) cout << (#x) << " : " << x << endl;
#define ll long long
#define ld long double

#define mp make_pair
#define ff first
#define ss second
#define pii pair<ll, ll>
#define sq(x) ((x) * (x))
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
const ll MOD = 1000 * 1000 * 1000 + 7;
using namespace std;



ll dp[1010][1010]={0};

int N;


int H,W;


char A[1005][1005];


ll seno(ll idx1, ll idx2)
{
  
if(dp[idx1][idx2]!=-1)
return dp[idx1][idx2];	

if (idx1==H&&idx2==W)
return dp[H][W]=1;	

ll x=0;

if (idx2+1<=W)
{	
if (A[idx1][idx2+1]=='.')
{x=(x+seno(idx1,idx2+1))%MOD;
	
}
}	

if (idx1+1<=H)
{	
if (A[idx1+1][idx2]=='.')
{
   x=(x+seno(idx1+1,idx2))%MOD;

}	
}

return dp[idx1][idx2]=x;

}



int main() 
{ 



fastio();

cin>>H>>W;
	
for (int i=1;i<=H;i++)
{
for (int j=1;j<=W;j++)
cin>>A[i][j],dp[i][j]=-1;	
}	




ll x=seno(1,1);

cout<<x;

return 0;
} 




Measured memory_bytes: 9216
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
string S[500]; bool W[26][26]; int n;
vector<int>X[26];
bool SearchingHeiro(int m) {
	int dist[1000];
	for (int i = 0; i < m; i++) {
		queue<int>Q;
		for (int j = 0; j < m; j++)dist[j] = 0;
		Q.push(i); int cnt = 0;
		while (!Q.empty()) {
			cnt++; int a1 = Q.front(); Q.pop();
			if (cnt >= 100000) { return true; }
			for (int j = 0; j < X[a1].size(); j++) {
				if (dist[X[a1][j]] > dist[a1] - 1) {
					dist[X[a1][j]] = dist[a1] - 1;
					Q.push(X[a1][j]);
				}
			}
		}
	}
	return false;
}
bool solve() {
	for (int i = 0; i < 676; i++) { X[i / 26].clear(); W[i / 26][i % 26] = false; }
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int Y = min(S[i].size(), S[j].size());
			for (int k = 0; k < Y + 1; k++) {
				if (k == Y) {
					if (S[i].size() > S[j].size())return false;
					break;
				}
				if (S[i][k] > S[j][k]) { W[S[i][k] - 'a'][S[j][k] - 'a'] = true; break; }
				if (S[i][k] < S[j][k]) { W[S[i][k] - 'a'][S[j][k] - 'a'] = true; break; }
			}
		}
	}
	for (int i = 0; i < 26; i++) {
		for (int j = 0; j < 26; j++) {
			if (W[i][j] == true)X[i].push_back(j);
		}
	}
	if (SearchingHeiro(26) == true)return false;
	return true;
}
int main() {
	while (true) {
		cin >> n; if (n == 0)break;
		for (int i = 0; i < n; i++)cin >> S[i];
		bool ans = solve();
		if (ans == true)cout << "yes" << endl;
		if (ans == false)cout << "no" << endl;
	}
	return 0;
}

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

int main(){
  int n; cin >> n;
  while(n--){
    int y,m,d;
    cin >> y >> m >> d;
    int sum = 0;
    for(int i=y;i<1000;i++){
      if(i == y){
	if(i%3 == 0){
	  sum += 21 - d;
	  sum += (10-m)*20;
	}
	else {
	  for(int j=m;j<=10;j++){
	    if(j == m) sum += 1 - d;
	    if(j%2 == 1) sum += 20;
	    else sum += 19;
	  }
	}
      }
      else if(i % 3 == 0) {
	sum += 10*20;
      }
      else {
	for(int j=1;j<=10;j++){
	  if(j%2 == 1) sum += 20;
	  else sum += 19;
	}
      }
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 1160