akhauriyash/Code-Regression huggingface dataset:
import java.io.PrintWriter;
import java.util.*;

public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = sc.nextInt();

        String s = sc.next();

        int totalR = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') totalR++;
        }

        int countR = 0;
        for (int i = 0; i < totalR; i++) {
            if (s.charAt(i) == 'R') countR++;
        }
        System.out.println(totalR - countR);
        // out.println("Hello World");
        out.flush();
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


Measured memory_bytes: 40752
#include <iostream>
using namespace std;
const int N = 100;

int main (){
    int M[N][N] = {0};
    int n,u,k,v;
    cin >> n;

    for (int i = 0; i < n ; ++i) {
     cin >> u >> k;
        u--; //0?????????????????????
        for (int j = 0; j < k ; ++j) {
            cin >> v;
            v -- ; // 0?????????????????????
            M[u][v] = 1; //u??¨v?????????????????????
        }
    }

    for (int i = 0; i < n ; ++i) {
        for (int j = 0; j < n; ++j) {
            if (j)  cout << " ";
            cout << M[i][j];
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
/*
#include<iostream>
#include<vector>
#include<algorithm>
 */
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep3(i, l, n) for (int i = l; i < n; ++i)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) rep(_, n) cout << a[_] << " "; cout << endl
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)

int main() {
    string str;
    cin >> str;
    ll sum = 0;
    rep(i, (1 << (SZ(str) - 1))) {
        string t = "";
        rep(j, SZ(str) - 1) {
            t += str[j];
            if (i & (1 << j)) {
                t += '+';
            }
        }
        t += str[SZ(str) - 1];
        int b = 0;
        for (int i = SZ(t) - 1; i >= 0; --i) {
            if (t[i] == '+') {
                b = 0;
                continue;
            }
            sum += (t[i] - '0') * pow(10, b++);
        }
    }
    out(sum);
}


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

vector<vector<int>> field(100, vector<int>(100));
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
void dfs(int y, int x) {
    field[y][x] = 0;
    for (int i = 0; i < 8; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (!field[ny][nx]) continue;
        if (field[ny][nx]) dfs(ny, nx);
    }
}

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

    int W, H;
    while (1) {
        cin >> W >> H;
        if (!W & !H) break;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                cin >> field[i][j];
            }
        }
        int cnt = 0;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if (field[i][j] == 1) {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << endl;
    }
}


Measured memory_bytes: 3264
#include<stdio.h>
#include<string.h>
int main()
{
  char c[100];
  int len,tr=1,n=1;
  scanf("%s",c);
  len=strlen(c);
  while((tr==1)&&(n<=len/4+1))
  {
    if((c[n-1]!=c[(len+1)/2-n-1])||(c[(len+1)/2-n-1]!=c[(len+1)/2+n-1])||(c[(len+1)/2+n-1]!=c[len-n]))
      tr=0;
    n++;
  }
  if(tr==1)
    printf("Yes");
  else
    printf("No");
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define ins insert
#define Pq priority_queue
#define u_set unordered_set
#define MOD 1000000007
#define MAXN 100001
#define set_val(arr,v) memset(arr, v, sizeof(arr))
#define FOR(i,from,to) for(int i=from; i<to; i++)
#define FOL(i,from,to) for(int i=from; i>=to; i--)
#define B() begin()
#define E() end()
#define F first
#define S second


int main() {
	ios::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
	ll h;
	cin >> h;
	ll res = 0, p = 1;
	while(h) {
		res += p;
		h /= 2;
		p *= 2; 
	}
	cout << res << endl;
	return 0; 
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
double f[1005][1005],dis[1005],a[1005][3];
bool b[1005];
int main()
{
	int i,j,k,n;
	double xi,xs,ys,xt,yt;
	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);
	scanf("%d",&n);
	a[0][0]=xs;a[0][1]=ys;a[0][2]=0;
	a[n+1][0]=xt;a[n+1][1]=yt;a[n+1][2]=0;
	for(i=1;i<=n;i++)
		scanf("%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2]);
	n++;
	for(i=0;i<=n;i++)
		for(j=i+1;j<=n;j++){
			f[i][j]=f[j][i]=max(0.0,sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))-(a[i][2]+a[j][2]));
		}
	for(i=0;i<=1003;i++) dis[i]=1e18;
	dis[0]=0;
	for(i=0;i<n;i++){
		xi=1e18;
		k=0;
		for(j=0;j<=n;j++){
            if(b[j]==0&&dis[j]<xi){
				xi=dis[j];
				k=j;
			}
        }
		b[k]=1;
		for(j=0;j<=n;j++)
			dis[j]=min(dis[j],dis[k]+f[k][j]);
	}
	printf("%.9lf",dis[n]);
}


Measured memory_bytes: 8064
using System;

namespace ABC_088_A_Csharp_ver
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int A = int.Parse(Console.ReadLine());
            if (N % 500 <= A)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
            Console.ReadKey();
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int n,k;
    cin>>n>>k;
    long long int h[n];
    for(int i=0;i<n;i++)
    cin>>h[i];
    long long int dp[n];
    dp[0]=0;
    dp[1]=h[1]-h[0];
    if(dp[1]<0)
    dp[1]*=-1;
    for(int i=2;i<n;i++){
        long long int temp;
        dp[i]=9223372036854775807;
        for(int j=1;j<=k&&i-j>=0;j++){
            if(h[i]>h[i-j])
            temp=dp[i-j]+h[i]-h[i-j];
            else
            temp=dp[i-j]-h[i]+h[i-j];
            if(temp<dp[i])
            dp[i]=temp;
        }
    }
    cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>//头文件
using namespace std;
long long Q,H,S,D,N,ans;//一定要long long
int main(){
    cin>>Q>>H>>S>>D>>N;
    ans=(N%2==0)?(min(min(min(Q*8,H*4),S*2),D)*N/2):(min(min(Q*4,H*2),S)+min(min(min(Q*8,H*4),S*2),D)*(N-1)/2);//为什么不能直接输出，是我的问题吗
    cout<<ans<<endl;//可以不打回车
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(void)
{
	int mat[16][16];
	int n;
	int i, j;

	while (scanf("%d", &n),n){
		memset(mat, 0, sizeof(mat));
		for (i = 0; i < n; i++){
			for (j = 0; j < n; j++){
				scanf("%d", &mat[i][j]);
				mat[i][n] += mat[i][j];
				mat[n][j] += mat[i][j];
				mat[n][n] += mat[i][j];
			}
		}
		for (i = 0; i <= n; i++){
			for (j = 0; j <= n; j++){
				printf("%5d", mat[i][j]);
			}
			puts("");
		}
	}
	return (0);
}

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

using namespace std;

const int INF = 1 << 29;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  int find(int k)
  {
    return (data[k] < 0 ? k : data[k] = find(data[k]));
  }

  void unite(int x, int y)
  {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
};

vector< pair< int, int > > g[100001];
vector< int > leftt[100001], rightt[100001], just[100001];
vector< int > gg[100001];
int deg[100001];


int rec(int idx, int back = -1)
{
  if(back != -1) {
    int tmp = max(leftt[idx][back], rightt[idx][back + 1]);
    if(tmp != INF) return (tmp);
  }
  if(rightt[idx][0] == INF) {
    for(int i = 0; i < g[idx].size(); i++) {
      int to, rev;
      tie(to, rev) = g[idx][i];
      if(i == back || just[idx][i] != INF) continue;
      just[idx][i] = rec(to, rev) + 1;
    }
    for(int i = 0; i < g[idx].size(); i++) {
      leftt[idx][i + 1] = max(leftt[idx][i], just[idx][i]);
    }
    for(int i = (int) g[idx].size() - 1; i >= 0; i--) {
      rightt[idx][i] = max(rightt[idx][i + 1], just[idx][i]);
    }
  }

  if(back == -1) return (rightt[idx][0]);
  return (max(leftt[idx][back], rightt[idx][back + 1]));
}


int main()
{
  int N, M;
  vector< pair< int, int > > edges, arcs;

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

  UnionFind uf(N);

  for(int i = 0; i < M; i++) {
    int x, y, t;
    cin >> x >> y >> t;
    --x, --y;
    if(t == 1) {
      arcs.emplace_back(x, y);
      g[x].emplace_back(y, -1);
    } else {
      if(uf.find(x) == uf.find(y)) {
        cout << "Infinite" << endl;
        return (0);
      }
      uf.unite(x, y);
      edges.emplace_back(x, y);
      g[y].emplace_back(x, g[x].size());
      g[x].emplace_back(y, g[y].size() - 1);
    }
  }

  {
    for(auto &e : arcs) {
      gg[uf.find(e.first)].push_back(uf.find(e.second));
      ++deg[uf.find(e.second)];
    }
    vector< int > order;
    for(int i = 0; i < N; i++) {
      if(deg[i] == 0) order.push_back(i);
    }
    for(int i = 0; i < order.size(); i++) {
      for(auto &e : gg[order[i]]) {
        if(--deg[e] == 0) order.push_back(e);
      }
    }
    if(order.size() != N) {
      cout << "Infinite" << endl;
      return (0);
    }
  }


  int ret = 0;
  for(int i = 0; i < N; i++) {
    int sz = g[i].size();
    just[i].assign(sz, INF);
    leftt[i].assign(sz + 1, INF);
    rightt[i].assign(sz + 1, INF);
    leftt[i][0] = rightt[i][sz] = 0;
  }
  for(int i = 0; i < N; i++) ret = max(ret, rec(i));
  cout << ret << endl;
}

Measured memory_bytes: 35520
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>s;
    a=(s[5]-'0');b=(s[6]-'0');
    pos=10*a+b;
    if(pos<=4)Cout("Heisei");
    else Cout("TBD");
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int n;
  scanf("%d", &n);
  int i, j;
  int r = 100000;
  int a, b;
  int digA, digB;
  int sum, sumA, sumB;
  for(i = 1; i < n; i++) {
    a = i, b = n - i;
    sumA = sumB = 0;
    while(a) {
      digA = a % 10;
      sumA += digA;
      a /= 10;
    }
    while(b) {
      digB = b % 10;
      sumB += digB;
      b /= 10;
    }
    sum = sumA + sumB;
    if(r > sum) r = sum;
  }
  printf("%d\n", r);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=105;
char s[maxn];
int n,a[maxn];
int work() {
	rep(i,1,n) {
		int k;
		for(k=1;k<=n-i+1;++k)
			if(!a[k]) break;
		if(k==n-i+2) return i-1;
		for(k=1;k<=n-i;++k)
			a[k]=max(a[k],a[k+1]);
	}
	return n;
}
int main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	int ans=n;
	rep(i,0,25) {
		rep(j,1,n)
			a[j]=(s[j]=='a'+i);
		ans=min(ans,work());
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> /*7C*/
using namespace std; 
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){

int r,c;
cin >> r >> c;

vector<vector<int>> x(r+1,vector<int>(c+1,0));

rep(i, r){
    rep(j, c){
        cin >> x.at(i).at(j);
    }
}

rep(i, r){
    rep(j, c){
        x.at(i).at(c) += x.at(i).at(j);
    }
}

rep(i, c+1){
    rep(j, r){
        x.at(r).at(i) += x.at(j).at(i);
    }
}

rep(i, r+1){
    rep(j, c+1){
        cout << x.at(i).at(j);
        if(j != c) cout << ' ';
    }
    cout << endl;
}
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;

#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << ", " << #y << "=" << y << endl

void solve() {
  ll a, b, c, d; cin >> a >> b >> c >> d;
  ll ans = a * c;
  ans = max(ans, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ll test = 1;
  // cin >> test;
  while (test--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3604
#include "bits/stdc++.h"
using namespace std;

////////////// Prewritten code follows. Look down for solution. ////////////////
#define x first
#define y second
#define len(x) ((int)(x).size())
using pii = pair<int, int>;
using ll = long long;
using llu = long long unsigned;
using ld = long double;

const ld EPS = 1e-9;
inline int cmp(ld x, ld y = 0, ld tol = EPS) {
	return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

const int MOD = 1e9+7;
inline int mod (ll x, int m = MOD) {
	return (int)(((x%m) + m)%m);
}

////////////////////////// Solution starts below. //////////////////////////////

const int N = 110, K = 1e5+10;

int n, k;
int a[N];
int pd[N][K];

int main () {
	scanf ("%d %d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf ("%d", &a[i]);
	
	for (int j = 0; j <= a[1]; j++)
		pd[1][j] = 1;
	for (int i = 2; i <= n; i++) {
		pd[i][0] = 1;
		int acu = 1;
		for (int j = 1; j <= k; j++) {
			acu = mod (acu + pd[i-1][j]);
			if ((j-a[i]-1) >= 0) acu = mod (acu - pd[i-1][j-a[i]-1]);
			pd[i][j] = acu;
		}
	}
// 	for (int i = 1; i <= n; i++) {
// 		for (int j = 0; j <= k; j++)
// 			printf ("%d ", pd[i][j]);
// 		putchar ('\n');
// 	}
	
	printf ("%d\n", pd[n][k]);

	return 0;
}


Measured memory_bytes: 40832
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000000; 
const int N=100000;
int a,b,c,ans;
inline int read()
{   int x=0,f=1;  char ch;
    ch=getchar();
    while (ch>'9' || ch<'0') {  if (ch=='-') f=-1; ch=getchar(); }
	while (ch<='9'&& ch>='0') {  x=x*10+ch-'0'; ch=getchar(); }
	return f*x; 
}
signed main()
{  a=read(); b=read(); c=read();
   ans=min(a+b+1,c);
   ans+=b;
   cout<<ans<<endl;
 } 

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

int f(int n) {
  int c = 0;
  while (n % 2 == 0) {
    n /= 2;
    c++;
  }
  return c;
}

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

  vector<int> a(N);
  rep(i, N) cin >> a[i];

  int ans = 0;
  rep(i, N) ans += f(a[i]);

  cout << ans << endl;
}

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

int main() {
	long x;
	cin >> x;
	long ans = 0;
	ans += x / 11;
	ans *= 2;
	if (x % 11 == 0);
	else if (x % 11 >= 7) ans += 2;
	else ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define MAXN 18

long long a[(1 << MAXN) + 5];
std::pair <long long, long long> v[(1 << MAXN) + 1][1 + MAXN];
inline void insert(int i, int aa, int j){
    if(i == v[aa][j].first || i == v[aa][j].second) return;
    int x = a[i];
    if(x >= a[v[aa][j].first])
        v[aa][j] = {i, v[aa][j].first};
    else if(x >= a[v[aa][j].second])
        v[aa][j] = {v[aa][j].first, i};
}
int main(){
    FILE*fi,*fo;
    //fi = fopen("a.in","r");
    //fo = fopen("a.out","w");
    fi = stdin;
    fo = stdout;

    int n;
    fscanf(fi,"%d", &n);
    for(int bits = 0; bits <= n; bits++)
        for(int config = 0; config < (1 << bits); config++)
            v[config][bits] = {1 << MAXN, 1 << MAXN};
    a[1 << MAXN] = -1;
    for(int i = 0; i < (1 << n); i++){
        fscanf(fi,"%d", &a[i]);
        for(int j = 0; j <= n; j++){
            int c = (i >> (n - j));
            insert(i, c, j);
        }
    }

    for(int bits = 0; bits <= n; bits++)
        for(int config = 1; config < (1 << bits); config++)
            for(int i = 0; i < n; i++)
                if(config & (1 << i)){
                    int nconfig = (config ^ (1 << i));
                    insert(v[nconfig][bits].first, config, bits);
                    insert(v[nconfig][bits].second, config, bits);
                }

    for(int i = 1; i < (1 << n); i++){
        long long max = a[v[i][n].first] + a[v[i][n].second];
        for(int j = 0; j <= n; j++)
            if(i & (1 << j))
                max = std::max(max, a[v[(i >> (j + 1)) * 2][n - j].first] + a[v[(i >> (j + 1)) * 2][n - j].second]);
        fprintf(fo,"%lld\n", max);
    }

    return 0;
}


Measured memory_bytes: 82944
#include <bits/stdc++.h>
using namespace std; 
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<long long> arr(n+1), score(n+1);
    for (int i=1; i<=n; i++)
        cin >> arr[i];
    for (int i=1 ; i<=n; i++)
        cin >> score[i];
    long long ans = LLONG_MIN;
    for (int i=1; i<=n; i++){
        long long cscore = 0, kl = k, maxi = LLONG_MIN, len = 0, ind = i;
        while (kl){
            ind = arr[ind];
            cscore += score[ind];
            maxi = max(maxi, cscore);
            kl--, len++;
            if(ind==i) break;
        }
        ans = max(ans, maxi);
        if (kl && cscore>0){
            if (kl>len) {
                long long mult = kl/len-1;
                cscore += cscore * mult;
                kl -= mult*len;
            }
            if (kl) {
                ind = i;
                long long temp = 0, maxi = 0;
                while (kl) {
                    ind = arr[ind];
                    temp += score[ind];
                    maxi = max(maxi, temp);
                    kl--;
                }
                cscore += maxi;
            }
        }
        ans = max(ans, cscore);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 3664
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace tes
{
	class contest
	{
		static void Main(string[] args)
		{
			 var s = Console.ReadLine();
            var num = int.Parse(Console.ReadLine());
            var c = s.ToArray();

            for(int i =0; i<c.Length; i++)
            {
				if (c[i] == 'a' && i != c.Length - 1) continue;
				
                int need = 26 - (c[i] - 'a');
                if(num>=need)
                {
                    c[i] = 'a';
                    num -= need;                        
                }

                if(i == c.Length-1 && num>0)
                {
                    if (num >= 26) num %= 26;
                    c[i] = (char)(c[i] + num);
                }
            }

            Console.WriteLine(new string(c));
		}		
		 
	}
}

Measured memory_bytes: 4312
#include<bits/stdc++.h>
using namespace std;
int n;
int m;
int mb[110000];
int dis[110000];
int v[110000];
int d[110000];
int c[110000];
struct KT
{
	int y;
	int next;
}f[210000];
int len;
int lin[210000];
void DJ(int xx,int yy)
{
	f[++len].next=lin[xx];
	f[len].y=yy;
	lin[xx]=len;
}
void KT(int x,int ys,int jl)
{
	if(!mb[x]) 
	mb[x]=ys;
	if(!jl||dis[x]>=jl) 
	return ;
	dis[x]=jl;
	for(int i=lin[x];i;i=f[i].next)
	{
		int y=f[i].y;
		KT(y,ys,jl-1) ;
	}
}
int q;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u;
		int v;
		cin>>u>>v;
		DJ(u,v);
		DJ(v,u);
	}
	cin>>q;
	for(int i=1;i<=q;i++) 
	{
		cin>>v[i]>>d[i]>>c[i];
	}
	
	for(int i=q;i>=1;i--) 
	{
		KT(v[i],c[i],d[i]);
	}
	for(int i=1;i<=n;i++) 
	{
		cout<<mb[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 4736
/*dismint|jjc*/
#include <bits/stdc++.h>
using namespace std;

#define io(F) string t_="";ifstream fin(t_+F+".in");ofstreamfout(t_+F+".out")
#define qio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define forl(V, S, E) for(int V = S; V < E; V++)
#define ford(V, S, E) for(int V = S; V >= E; V--)
#define fore(E, X) for(auto &E:X)
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
#define graph unordered_map<int, unordered_set<int>>
typedef long long ll;

int main() {
	double ans = 3.1415926535;
	double r; cin >> r;
	ans *= 2*r;
	println(ans);
}


Measured memory_bytes: 3784
#ABC054b
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]


def match(x, y):
    for i in range(m):
        for j in range(m):
            if (a[y + i][x + j] != b[i][j]):
                return False
    return True


for i in range(n - m + 1):
    for j in range(n - m + 1):
        if (a[i][j] == b[0][0] and match(i, j)):
            print("Yes")
            exit(0)
print("No")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define MAXN 200005
#define INF 100000000
#define MOD 998244353
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,a[MAXN],b[MAXN];
bool check(int x)
{
    return b[x]>a[x]&&b[x]>b[x==1?n:x-1]+b[x==n?1:x+1];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    ll ans=0;
    queue<int> que;
    for(int i=1;i<=n;i++)
        if(b[i]>a[i]&&check(i))
            que.push(i);
    while(que.size())
    {
        int p=que.front(); que.pop();
        if(!check(p)) continue;
        int l=(p==1?n:p-1),r=(p==n?1:p+1);
        int x=b[p]-a[p];
        int round=x/(b[l]+b[r]);
        ans+=round;
        b[p]-=round*(b[l]+b[r]);
        if(round)
        {
            if(check(l)) que.push(l);
            if(check(r)) que.push(r);
        }
    }
    for(int i=1;i<=n;i++)
        if(a[i]!=b[i])
        {
            puts("-1");
            return 0;
        }
    printf("%lld\n",ans);
    return 0;
}


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

int main(void){
  string S;
  cin >> S;
  char one, two;
  one = S.at(0);
  two = S.at(1);
  if(one == 'M') cout << 6 << endl;
  else if(one == 'T' && two == 'U') cout << 5 << endl;
  else if(one == 'W') cout << 4 << endl;
  else if(one == 'T' && two == 'H') cout << 3 << endl;
  else if(one == 'F') cout << 2 << endl;
  else if(one == 'S' && two == 'A') cout << 1 << endl;
  else cout << 7 << endl;
}

Measured memory_bytes: 256
#include<cstdio>
using namespace std;
long long n,a,b,maxx,minn;
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	if (a>b||(n==1&&a!=b)) {printf("0\n");return 0;}
	minn=(n-1)*a+b;
	maxx=(n-1)*b+a;
	printf("%lld\n",maxx-minn+1);
}

Measured memory_bytes: 128
#include<stdio.h>

int main(void){
    int w,h,x,y,r;

    scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
    if(x + r <= w && x - r >= 0 && y + r <= h && y - r >= 0)
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}

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

string s;
int k;

set<string> str_set;
string ans;

int main(void){
  cin >> s;
  scanf("%d", &k);

  for (int i = 0; i < s.size(); ++i) {
    string cur("");
    int size = s.size();
    int bound = min(i + k, size);
    for (int j = i; j < bound; ++j) {
      cur.push_back(s[j]);
      str_set.insert(cur);
    }
  }

  int i = 0;
  for (auto str: str_set) {
    if (i == k - 1) {
      ans = str;
      break;
    }
    i += 1;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1664
N = gets.chomp.to_i
l = []
r = []
N.times do |n|
  l[n],r[n] = gets.chomp.split(" ").map(&:to_i)
end
seated = 0
N.times do |n|
  seated += r[n-1] - l[n-1] + 1
end
print("#{seated}")

Measured memory_bytes: 1788
n = int(input())
lis = []
li = []
l = []
cou = 0
for i in range(n):
  a,b = map(str,input().split())
  if a not in li:
    lis.append([[int(b),i+1]])
    li.append(a)
    l.append([a,cou])
    cou += 1
  else:
    lis[li.index(a)].append([int(b),i+1])
l.sort()
for i in range(len(l)):
  lis[l[i][1]].sort(reverse=True)
  for num,nu in lis[l[i][1]]:
    print(int(nu))

Measured memory_bytes: 3064
// God put a smile upon your face <3

#include <bits/stdc++.h>

#define slld(longvalue) scanf("%lld", &longvalue)

#define ll long long
#define ull unsigned long long
#define pll pair < long long, long long >

#define fastio ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0)

#define pb push_back

#define bug printf("BUG\n")

#define mxlld LLONG_MAX
#define mnlld -LLONG_MAX

#define mxd 2e8
#define mnd -2e8

#define pi 3.14159265359

using namespace std;

bool check(ll n, ll pos)
{
	return n & (1LL << pos);
}

ll Set(ll n, ll pos)
{
	return n = n | (1LL << pos);
}

ll arr[200005];
ll sum[200005];

int main()
{
    ll i, j, k, l, m, n, o, r, q;
    ll testcase;
    ll input, flag, tag, ans;

//    freopen("input.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

    while(cin >> n)
    {
		m = (1e9) + 7;

		for(ll i = 1; i <= n; i++)
		{
			cin >> arr[i];

			sum[i] = arr[i];
		}

		sum[n + 1] = 0;

		for(ll i = n; i >= 1; i--) sum[i] += sum[i + 1];

		ans = 0;

		for(ll i = 1; i <= n; i++)
		{
			ans = (ans + (arr[i] * (sum[i + 1] % m))) % m;
		}

		cout << ans << "\n";
	}


}






Measured memory_bytes: 6708
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}
ll kai(vector<ll> A, ll key) {
	ll an = 0;
	rep(i, A.size()) {
		an += (A.at(i) - 1) / key;
	}
	return an;
}
// index が条件を満たすかどうか
bool isOK(int index,vector<ll> A, int K) {
	if (kai(A,index) <= K) return true;
	else return false;
}

// 汎用的な二分探索のテンプレ
int binary_search(ll MA,vector<ll> A,ll K) {
	int left = 0; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = MA; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, A,K)) right = mid;
		else left = mid;
	}

	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
vector<ll> fact, factinv, inv;
ll mod = 1e9 + 7;
void prenCkModp(ll n) {
	fact.resize(n + 5);
	factinv.resize(n + 5);
	inv.resize(n + 5);
	fact.at(0) = fact.at(1) = 1;
	factinv.at(0) = factinv.at(1) = 1;
	inv.at(1) = 1;
	for (ll i = 2; i < n + 5; i++) {
		fact.at(i) = (fact.at(i - 1) * i) % mod;
		inv.at(i) = mod - (inv.at(mod % i) * (mod / i)) % mod;
		factinv.at(i) = (factinv.at(i - 1) * inv.at(i)) % mod;
	}

}
ll nCk(ll n, ll k) {
	if (n < 0 || k < 0){
		return 1;
	}
	else if (n < k) {
		return 0;
	}
	return fact.at(n) * (factinv.at(k) * factinv.at(n - k) % mod) % mod;
}

ll dp[51][51][2501];

int main() {
	ll N, A;
	cin >> N >> A;
	ll MA = A;
	vector<ll> x(N);
	rep(i, N) {
		cin >> x.at(i);
		MA = max(MA, x.at(i));
	}
	for (ll j = 0; j <= N; j++) {
		for (ll k = 0; k <= N; k++) {
			for (ll s = 0; s <= N*MA; s++) {
				if (j == 0 && k == 0 && s == 0) {
					dp[j][k][s] = 1;
				}
				else if (j >= 1 && s < x.at(j-1)) {
					dp[j][k][s] = dp[j-1][k][s];
				}
				else if (j >= 1 &&k>=1&& s >= x.at(j-1)) {
					dp[j][k][s] = dp[j - 1][k][s]+ dp[j - 1][k-1][s-x.at(j-1)];
				}
				else {
					dp[j][k][s] = 0;
				}
			}
		}
	}
	ll an = 0;
	for (ll k = 1; k <= N; k++) {
		an += dp[N][k][k * A];
	}
	cout << an << endl;
 }


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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 200100;
vi a[N], b[N];
int da[N], db[N];
int n;
int X, Y;
const int inf = 1e9;

void dfs(int v, int pr, int dst, vi a[], int d[]) {
	d[v] = dst;
	forn(i, sz(a[v])) {
		int to = a[v][i];
		if (to != pr) {
			dfs(to, v, dst + 1, a, d);
		}
	}
}

bool good[N];
set<int> be[N];
int ans;

void precalc(int v, int pr) {
	bool ok = 1;
	forn(i, sz(b[v])) {
		int to = b[v][i];
		if (to == pr || be[to].find(pr) != be[to].end()) {
			ok = 0;
			 break;
		}
	}
	if (ok && pr >= 0) {
		good[v] = 1;
		good[pr] = 1;
	}
	forn(i, sz(a[v])) {
		int to = a[v][i];
		if (to != pr)
			precalc(to, v);
	}
}

void calc(int v, int pr) {
	if (good[v]) {
		ans = inf;
		return;
	}
	umx(ans, db[v]);
	forn(i, sz(a[v])) {
		int to = a[v][i];
		if (to == pr)
			continue;
		if (db[to] > da[to]) {
			calc(to, v);
		}
	}
}	

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n >> X >> Y;
	X--, Y--;
	forn(i, n - 1) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		a[u].pb(v);
		a[v].pb(u);
	}
	memset(good, 0, sizeof(good));
	forn(i, n - 1) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		b[u].pb(v);
		b[v].pb(u);
		be[u].insert(v);
		be[v].insert(u);
	}
	ans = 0;
	dfs(X, -1, 0, a, da);
	dfs(Y, -1, 0, b, db);
	precalc(X, -1);
	calc(X, -1);
	if (ans == inf) {
		cout << -1 << endl;
	} else {
		cout << 2 * ans << endl;
	}
	return 0;
}


Measured memory_bytes: 66172
#include <iostream>
using namespace std;
typedef long long ll;
const ll Mod = (ll)(1e9) + 7;

int main() {
  ll a;
  int N, k, j;
  ll A[60][2] = { };
  ll x[60] = { };
  cin >> N;
  k = 0;
  while (cin >> a) {
    for (j = 0; j < 60; a >>= 1, j++) {
      A[j][a & 1]++;
    }
    k++;
    if (k >= N) {
      break;
    }
  }
  for (int i = 0; i < 60; i++) {
    x[i] = (A[i][0] * A[i][1]);
  }
  ll y = 0;
  for (int i = 0; i < 60; i++) {
    y += (x[i] % Mod * ((1LL << i) % Mod)) % Mod;
    y %= Mod;
  }
  cout << y << endl;
  return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#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 ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define yes(n) cout << ((n) ? "yes" : "no"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define VVi vector<vector<ll>>
#define Vd vector<double>
#define Vb vector<bool>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<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;}

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,b=0,c=0,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN(n);
  VVi a(n+1000, vector<int>(3));
  REP(i,n){
    REP(j,3){
      IN(a[i][j]);
    }
  }
  int dp[n+1000][3];
  REP(i,n){
    REP(j,3){
      REP(k,3){
        if (j==k) continue;
        chmax(dp[i+1][k], dp[i][j] + a[i][k]);
      }
    }
  }
  int res = 0;
  REP(i,3) chmax(res, dp[n][i]);
  OUT(res);
}

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

char str[100];
int a[50][100];
int main(){
	int n, cnt = 'z'-'a';
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%s", str);
		int m = strlen(str);
		for(int j = 0;j < m;j++){
			a[i][str[j]-'a']++;
		}
	}
	
	for(int i = 0;i < cnt+1;i++){
		int mn = 1e9;
		for(int j = 0;j < n;j++){
			mn = min(mn, a[j][i]);
		}
		for(int j = 0;j < mn;j++)printf("%c", 'a'+i);
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 256
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

struct Solve {
    N: usize,
    M: usize,
    Q: usize,
    a: Vec<usize>,
    b: Vec<usize>,
    c: Vec<usize>,
    d: Vec<usize>,
    A: Vec<usize>,
}

impl Solve {
    fn new(
        N: usize,
        M: usize,
        Q: usize,
        a: Vec<usize>,
        b: Vec<usize>,
        c: Vec<usize>,
        d: Vec<usize>,
    ) -> Solve {
        Solve {
            N,
            M,
            Q,
            a,
            b,
            c,
            d,
            A: vec![0; N],
        }
    }

    fn solve(&mut self) {
        let M = self.dfs(0, 1);
        println!("{}", M);
    }

    fn dfs(&mut self, i: usize, x: usize) -> usize {
        if i == self.N {
            return self.calc();
        }

        let mut M = 0;

        for y in x..=self.M {
            self.A[i] = y;
            M = M.max(self.dfs(i + 1, y));
        }

        M
    }

    fn calc(&self) -> usize {
        (0..self.Q)
            .map(|i| {
                if self.A[self.b[i]] - self.A[self.a[i]] == self.c[i] {
                    self.d[i]
                } else {
                    0
                }
            })
            .sum()
    }
}

fn main() {
    let mut scan = Scan::new();

    let N = scan.word::<usize>();
    let M = scan.word::<usize>();
    let Q = scan.word::<usize>();
    let mut a = vec![];
    let mut b = vec![];
    let mut c = vec![];
    let mut d = vec![];

    for _ in 0..Q {
        a.push(scan.word::<usize>() - 1);
        b.push(scan.word::<usize>() - 1);
        c.push(scan.word::<usize>());
        d.push(scan.word::<usize>());
    }

    Solve::new(N, M, Q, a, b, c, d).solve();
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
using namespace std;
struct _I { _I() {cin.tie(0);ios::sync_with_stdio(false);}} __I;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define MOD 1000000007

int main()
{
    string s, t; cin >> s >> t;
    cout << t << s << endl;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
m = []
count = 0
for i in range(H):
    s = input()
    count += s.count('.')
    m.append(list(s))

que = [(0,0)]
keiro = {}
keiro[(0,0)] = 1
# print(m)
while que:
    h, w = que.pop(0)
    # print(h,w)
    if h+1 < H:
        if m[h+1][w] == '.':
            if (h+1,w) in keiro:
                keiro[(h+1,w)] = min(keiro[(h+1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h+1,w)] = keiro[(h,w)]+1
                que.append((h+1,w))
    if w+1 < W:
        if m[h][w+1] == '.':
            if (h,w+1) in keiro:
                keiro[(h,w+1)] = min(keiro[(h,w+1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w+1)] = keiro[(h,w)]+1
                que.append((h,w+1))
    if h-1 >= 0:
        if m[h-1][w] == '.':
            if (h-1,w) in keiro:
                keiro[(h-1,w)] = min(keiro[(h-1,w)],keiro[(h,w)]+1)
            else:
                keiro[(h-1,w)] = keiro[(h,w)]+1
                que.append((h-1,w))
    if w-1 >= 0:
        if m[h][w-1] == '.':
            if (h,w-1) in keiro:
                keiro[(h,w-1)] = min(keiro[(h,w-1)],keiro[(h,w)]+1)
            else:
                keiro[(h,w-1)] = keiro[(h,w)]+1
                que.append((h,w-1))

if (H-1,W-1) in keiro:
    print(count-keiro[(H-1,W-1)])
else:
    print(-1)




Measured memory_bytes: 41836
## coding: UTF-8
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

A = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

prim = factorization(A) 
#print(prim)
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

def count_parts(N):
    #整数Nを引数として、それが何このパーツに分解できるか返す
    #N=1~40
    if(N<3):
        return 1
    elif(N<6):
        return 2
    elif(N<10):
        return 3
    elif(N<15):
        return 4
    elif(N<21):
        return 5
    elif(N<28):
        return 6
    elif(N<36):
        return 7
    elif(N<45):
        return 8

ans = 0
#40乗まで考えれば良い
for i in range(len(prim)):
    s = prim[i][1]
    ans += count_parts(s)

if(A == 1):
    ans = 0

print(ans)




Measured memory_bytes: 63568
# include <stdio.h>
# include <math.h>

int main(){
	int count=0;
	double a,b;
/*	double tempa=0,tempb=0;store a and b*/
	
while (scanf("%lf %lf",&a,&b)!=EOF){
	double GCD,LCM;
	double tempa=0,tempb=0; /*store a and b*/
	tempa=a;
	tempb=b;
	while (count==0){
		a=fmod(a,b);
/*		a=a%b;*/
		if (a==0){
			GCD=b;
			count=1;
		}
		else{
			b=fmod(b,a);
/*			b=b%a;*/
			if (b==0){
				GCD=a;
				count=1;
			}
		}
	}
LCM=(tempa/GCD)*(tempb/GCD)*GCD;
printf("%.0f %.0f\n",GCD,LCM);
count=0;	
}
return 0;
}


Measured memory_bytes: 2020
// A.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

int main(int argc, char *argv[]) {
	string s;
	cin >> s;
	char prev = 0;
	string ans = "Good";
	for (char c : s) {
		if (c == prev) {
			ans = "Bad";
		}
		prev = c;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<set>
#include<bitset>
#include <sstream>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;

int main()
{
    int N;
    set<string> siri;
    bool flag=true;
    string nowword,prevword;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>nowword;
        siri.insert(nowword);
        if(i==0)
        {
            prevword=nowword;

            continue;
        }
        int prevlength=prevword.length();

        
        if(prevword.substr(prevlength-1,1)!=nowword.substr(0,1))
        {
            flag=false;
        }
        prevword=nowword;

    }
    if(flag && siri.size()==N)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define COUT(x) cout<<(x)<<"\n"

int main(){
    int x,y;
    cin >> x >> y;
    for(int i=2*x;i<=4*x;i+=2){
        if(i==y){
            COUT("Yes");
            return 0;
        }
    }
    COUT("No");
    return 0;
}

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

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> p(n);
  for(int i=0;i<n;i++) cin>>p.at(i);
  sort(p.begin(),p.end());
  int def=1000000000;
  for(int i=0;i<=n-k;i++){
    def = min(def,p.at(i+k-1)-p.at(i));   
  }
  cout<<def<<endl;
  return 0;
}

Measured memory_bytes: 640
n = int(input())
keta = len(str(n))
if keta == 1:
	print(n)
elif keta == 2:
	print(9)
elif keta == 3:
	print(str(n-90))
elif keta == 4:
	print(str(909))
elif keta == 5:
	print(str(n-9090))
elif keta == 6:
	print(90909)

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

// {{{
template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar[0].size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}

template<typename T>
void unique(vector<T>& vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

template<typename T>
vector<T> cumsum(vector<T> vec){
    vector<T> newvec((T)vec.size());
    int tmp = 0;
    for (int i = 0; i < (int)vec.size(); i++) {
        tmp += vec[i];
        newvec[i] = tmp;
    }

    return newvec;
}

template<typename T>
T digitsum(T x){
    T y=0;
    while(x){
        y += x % 10;
        x /= 10;
    }

    return y;
}


// }}}
/* vim:set foldmethod=marker: */

void solve(){
    int w,h,n;
    cin >> w >> h >> n;

    int x1=0, x2=w, y3=0, y4=h;
    for (int i = 0; i < n; i++) {
        int x,y,a;
        cin >> x >> y >> a;
        if (a == 1) {
            x1 = max(x1, x);
        }else if (a== 2){
            x2 = min(x2, x);
        }else if (a== 3){
            y3 = max(y3, y);
        }else{
            y4 = min(y4, y);
        }
    }

    if (x1 >= x2 || y3 >= y4) {
        cout << 0 << endl;
    }else{
        cout << (x2 - x1) * (y4 - y3) << endl;
    }
    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int A[1000000], n;

/* 二分探索 */
int binarySearch(int key) {
  int left = 0;
  int right = n;
  int mid;
  while ( left < right ) {
    mid = (left + right) / 2;
    if ( key == A[mid] ) return 1;  /* key を発見 */
    if ( key > A[mid] ) left = mid + 1;  /* 後半を探索 */
    else if ( key < A[mid] ) right = mid;  /* 前半を探索 */
  }
  return 0;
}

int main() {
  int i, q, k, sum = 0;

  scanf("%d", &n);
  for ( i = 0; i < n; i++ )
    scanf("%d", &A[i]);

  scanf("%d", &q);
  for ( i = 0; i < q; i++ ) {
    scanf("%d", &k);
    if ( binarySearch( k ) ) sum++;
  }
  printf("%d\n", sum);

  return 0;
}


Measured memory_bytes: 2244
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;



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

    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    rep(i, N) cin >> a[i];

    vector<bool> dp(K+1); //! true: the first player wins
    dp[0] = false;
    for (int i = 1; i <= K; ++i) {
        bool win = false;
        rep(j, N) {
            int to = i - a[j];
            if (0 <= to && !dp[to]) {
                win = true;
                break;
            }
        }
        if (win) dp[i] = true;
    }


    cout << (dp[K] ? "First" : "Second") << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll                      long long int
#define pb                      push_back
#define mp                      make_pair
#define in                      insert
#define all(x)                  (x).begin(),(x).end() 
#define rep(i,a,n)              for(int i=0;i<n;++i)
#define per(i,a,n)              for(int i=n-1;i>=0;--i)
#define mod                     1000000007
using namespace std;

bool check(string str,int s,int e){

	int p=s,q=e;
	while(p<q){
		if(str[p]!=str[q]){
			return false;
		}
		p++;q--;
	}

	return true;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    string str;
    cin>>str;
    int n=str.length();
    if(check(str,0,n-1) and check(str,0,((n-1)/2)-1) and check(str,((n+3)/2)-1,n-1)){
    	cout<<"Yes\n";
    }
    else{
    	cout<<"No\n";
    }
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define mp make_pair

int main()
{
	int x;
	cin >> x;
	if(x>=30)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 3588