akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define per1(i,n) for(int i=n;i>0;i--)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll num[200001],numm[200001][2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m,X[200001];
    cin>>n>>m;
    rep(i,n) cin>>X[i],num[X[i]]++,numm[X[i]%m][0]++;
    rep1(i,100001) numm[i%m][1]+=num[i]/2*2;
    ll ans=0;
    rep(i,m/2+1){
        if(i==0||i==m-i) ans+=numm[i][0]/2;
        else{
            if(numm[i][0]>numm[m-i][0]) swap(numm[i],numm[m-i]);
            ans+=numm[i][0];
            numm[m-i][0]-=numm[i][0];
            if(numm[m-i][0]<numm[m-i][1]) ans+=numm[m-i][0]/2;
            else ans+=numm[m-i][1]/2;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 6776
package main

import "fmt"

func isEven(n int) bool { return n%2 == 0 }

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	if isEven(a) || isEven(b) {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
	}
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back


using namespace std;

void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {std::cout << x;}
void __print(unsigned x) {std::cout << x;}
void __print(unsigned long x) {std::cout << x;}
void __print(unsigned long long x) {std::cout << x;}
void __print(float x) {std::cout << x;}
void __print(double x) {std::cout << x;}
void __print(long double x) {std::cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i : x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
template <typename T> inline void inp(T &any) {cin >> any;} template <typename T, typename... U>inline void inp(T &a, U &...b) {cin >> a; inp(b...);}
#define rin(args...) ll args; inp(args);
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#define matdeb(mat,row,col) cout << #mat << "::" << endl; printmat(mat,row,col); printpartition;
#define debugv(v,n) cout << #v << ":" << endl; printv(v,0,n-1); printpartition;
#else
#define debug(x...)
#define matdeb(mat,row,col)
#define debugv(v,n)
#endif

const int maxm = 1000000000 + 7;

const ll MOD = 1e9 + 7;
const int INF = 55;
ll dp [INF] [INF * INF];

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}


//----------->CODE BEGINS --------------->


int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    IOS;



   int n,m; cin>>n>>m;

   char a[n][n], b[m][m];

   loop(i,n)
   {
    loop(j,n)
    {
        cin>>a[i][j];
    }
   }
 
   loop(i,m)
   {
    loop(j,m)
    {
        cin>>b[i][j];
    }
   }
  
   bool exist = false;

   loop(i,n)
   {
    loop(j,n)
    {
        if(i+m-1 >= n || j+m-1 >= n) continue;

        bool match = true;

        loop(y,m)
        {
            loop(z,m)
            {
                if(a[i+y][j+z] != b[y][z])
                    match = false;
            }
        }

        if(match) exist = true;
    }
   }
   

   if(exist) cout<<"Yes";

   else
   {
    cout<<"No";
   }


}


Measured memory_bytes: 3664
// AOJ 0571 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0571)
#include<algorithm>
#include<iostream>
#include<string>
#define rep(i,a) for(int i=0;i<(a);++i)

std::string s;

int main()
{
	std::cin >> s;

	int i = 0, ans = 0;
	while( i < s.size() )
	{
		while( i < s.size() && s[i] != 'J' )
			++i;

		int cnt[3] = {0};
		const std::string JOI = "JOI";

		rep( j, 3 ) while( i < s.size() && s[i] == JOI[j] )
			++i, ++cnt[j];

		if( cnt[0] >= cnt[1] && cnt[2] >= cnt[1] )
			ans = std::max( ans, cnt[1] );
	}
	
	std::cout << ans << std::endl;

	return 0;
}

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

int main() {
  int x,y;
  cin >> x >> y;
  int ans_x,ans_y;
  ans_x = -y+4*x;
  ans_y = y-2*x;
  if(ans_x % 2 == 0 && ans_x / 2 >= 0 && ans_y % 2 == 0 && ans_y / 2 >= 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return(0);
}

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

int main(){
  string S;
  cin >> S;
  bool hitachi = true;
  if( S.size() % 2 == 1){ hitachi = false;}
  else{
    rep(i,S.size() / 2){
      if( S.at(2*i) == 'h' && S.at(2*i +1) == 'i')continue;
      else hitachi = false;
    }
  }
  puts( hitachi ? "Yes" : "No" );
}
    

Measured memory_bytes: 256
from operator import itemgetter
import bisect


h, w, n = map(int, input().split())
info = [tuple(map(int, input().split())) for i in range(n)]

memo = set()
for i, j in info:
    memo.add(i * 10**6 + j)

pos = [[] for _ in range(w + 1)]
info = sorted(info, key = itemgetter(0))
for i, j in info:
    pos[j].append(i)

ans = 10**18
pos_i, pos_j = 1, 1
ind = bisect.bisect_right(pos[pos_j], pos_i)
try:
    ans = min(pos[pos_j][ind] - 1, ans)
except:
    pass

while True:
    if (pos_i + 1) * 10**6 + pos_j in memo or pos_i == h:
        ans = min(ans, pos_i)
        break
    pos_i += 1

    if pos_i * 10**6 + (pos_j + 1) in memo or pos_j == w:
        continue
    else:
        pos_j += 1
    ind = bisect.bisect_right(pos[pos_j], pos_i)
    try:
        ans = min(pos[pos_j][ind] - 1, ans)
    except:
        pass
print(ans)

Measured memory_bytes: 109008
#include<stdio.h>

int main()
{
	int n;
	int a[101];
	int cnt = 0;
	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		if(i % 2 == 1){
			if(a[i] % 2 == 1){
				cnt++;
			}
		}
	}
    printf("%d", cnt);
	
	
}

Measured memory_bytes: 1680
import math
N,D=map(int,input().split())
ans=0
pos=[]
for i in range(N): pos.append(list(map(int,input().split())))
for i in range(N):
    y=pos[i]
    for j in range(N):
        z=pos[j]
        if i==j: pass
        else:
            distance=0.0
            for k in range(D): distance+=(y[k]-z[k])**2
            if math.sqrt(distance).is_integer(): ans+=1
print(ans//2)

Measured memory_bytes: 3188
#include<stdio.h>
int a,s,d[1001],f[1001],g[1001][1001],h,z,i,j,x;
int main(void)
{
	x=0;
	scanf("%d",&a);
	while(a!=0){
		x++;
		scanf("%d",&s);
		for(i=0;i<s;i++){
			scanf("%d,%d",&d[i],&f[i]);
		}
		for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				g[i][j]=0;
			}
		}
		for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				if(g[i+1][j+f[i]]<g[i][j]+d[i]&&j+f[i]<=a){
					g[i+1][j+f[i]]=g[i][j]+d[i];
				}
				if(g[i+1][j]<g[i][j]){
					g[i+1][j]=g[i][j];
				}
			}
		}
	/*	for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				printf("%d ",g[i][j]);
			}
			printf("\n");
		}*/
		h=0;
		z=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d:\n",x);
		printf("%d\n%d\n",h,z);
		scanf("%d",&a);
	}

	return 0;
}

Measured memory_bytes: 4948
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  string s;
  cin >> s;
  string ans = "";
  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] == 'B')
      ans = ans.substr(0, ans.size() - 1);
    else
      ans += s[i];
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
  int A, B;
  cin >> A >> B;
  int  outlet = 0;
  int min_count = 0;
  
  while(outlet < B){
    if(min_count == 0) outlet += A;
    else outlet += A - 1;
    min_count += 1;
  }
  
  if(B == 1) min_count = 0;
  
  cout << min_count << endl;

  return 0;
}

Measured memory_bytes: 256
s = input()
length = len(s)
#print("length:",length)
first = s.index("A")
#print("first:",first)
s_rev = s[::-1]
#print(s_rev)
end_rev = s_rev.index("Z")
#print("end_rev",end_rev)
end = (length - 1) - end_rev
#print("end",end)
print(end-first + 1)


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

long long x, y;
int main() {
	cin >> x >> y;
	if(x%y==0) puts("-1");
	else {
		for(int i=2; ; i++) {
			if(x*i % y > 0) return printf("%lld", x*i) * 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define input(array) repi(array##_itr, array) { cin >> *(array##_itr); }
#define F first
#define S second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
string solve(bool a) { return ((a) ? "Yes" : "No"); }
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n;
	ll ans=INF;
	cin >>n;
	V a(n);
	input(a);
	ans = a[0];
	rep(i, n) { ans = __gcd(ans, a[i]); }
	cout<<ans<<endl;
}

Measured memory_bytes: 3956
#include<stdio.h>
int main(){
	int n,k,s[105],b[105],i,j,x;
	while(1){
		scanf("%d%d",&n,&k);
		if(n==0 && k==0)break;
		for(i=0;i<k;i++)scanf("%d",&s[i]),b[i]=0;
		for(i=0;i<n;i++){
			for(j=0;j<k;j++){
				scanf("%d",&x);
				b[j]+=x;
			}
		}
		x=0;
		for(i=0;i<k;i++)
			if(b[i]>s[i]){x=1;break;}
		if(x==1)printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

Measured memory_bytes: 384
input = raw_input
x, y = map(int, input().split(" "))

if x == 1 and y == 1:
    out = 3 * 2 + 4
else:
    out = 0
    if x == 1:
        out += 3
    elif x == 2:
        out += 2
    elif x == 3:
        out += 1

    if y == 1:
        out += 3
    elif y == 2:
        out += 2
    elif y == 3:
        out += 1

out *= 100000
print(out)

Measured memory_bytes: 27884
#include <bits/stdc++.h>
    #include <chrono>
  
    using namespace std;
    using namespace std::chrono; 
 
    typedef long long int ll;
 
    #define MOD (ll)(1e9+7)
    #define endl "\n"
    #define pb push_back
    #define TEST_CASES  ll t;cin>>t;while(t--)
    #define forn(i,a,n) for (ll i = a; i < n; ++i)
    #define f first
    #define s second
    #define all(x) x.begin(), x.end()
    
    ll powD(ll x,ll y){
      ll res = 1;
      while(y > 0){
        if(y & 1)
          res = (res*x)%MOD;
        x = (x*x)%MOD;
        y = y>>1;
      }
      return res;
    }

    ll MAX = 1e6;
    vector<bool> visited(MAX+1,false);
    void seive(ll n){
      forn(i,2,n+1){
        if(!visited[i]){
          for (int j = 2*i; j <= n ; j += i)
          {
            if(!visited[j])
              visited[j] = true;          
          }
        }
      }
    }

    int count(int n){
      return int((-1 + sqrt(1+8*n))/2);
    }

    int calc(ll n){
      seive(MAX);
      int ans = 0;
      forn(i,2,MAX+1){
        if(!visited[i]){
          if(n%i == 0){
            int cnt = 0;
            while(n%i == 0){
              cnt++;
              n /= i;
            }
            ans += count(cnt);
          }
        }
      }
      if(n > 1){
        ans += 1;
      }
      return ans;
    }

    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      ll n;
      cin>>n;
      cout<<calc(n)<<endl;
    }



Measured memory_bytes: 3804
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: u32,
        x: u32,
        t: u32
    }
    let ans = if n % x == 0 {t * (n/x)}
              else {t * (n/x) + t};
    println!("{}", ans);
}


Measured memory_bytes: 2152
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
long long a[200005];
long long dp[200005][5];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][0]=dp[i-1][0]+a[i];
		dp[i][1]=min(dp[i-1][0],dp[i-1][1])+((a[i]==0)?2:(a[i]%2));
		dp[i][2]=min(dp[i-1][1],dp[i-1][2])+((a[i]==0)?1:(a[i]+1)%2);
		dp[i][3]=min(dp[i-1][2],dp[i-1][3])+((a[i]==0)?2:(a[i]%2));
		dp[i][4]=min(dp[i-1][3],dp[i-1][4])+a[i];
		for(int j=1;j<=4;j++) dp[i][j]=min(dp[i][j],dp[i][j-1]);
	}
	cout<<dp[n][4];
}

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

using namespace std;

const int N = 110;

int n;
string s;

int main()
{
    cin >> n >> s;
    for(int i = 0; i < s.size(); i++)
    {
        char c = (s[i] - 'A' + n) % 26 + 'A';
        cout << c;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
const lli mod=1e9+7;
void fast() {std::ios::sync_with_stdio(false);cin.tie(NULL);}
lli power(lli a,lli b){lli ans=1;while(b!=0){ if(b%2==1){ans*=a;}b/=2;a*=a;} return ans;}
lli invmod(lli a) {return pow(a,mod-2);}
#define vi vector<int>
#define vlli vector<lli>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define si(n) scanf("%d",&n)
#define sli(n) scanf("%lld",&n)
#define printi(n) printf("%d\n",n)
#define printli(n) printf("%lld\n",n)
#define all(vi) (vi.begin(),vi.end())
#define forn(i,n) for(int i=0;i<n;i++)
void print(int a[],int n){for(int i=0;i<n;i++) cout<<a[i]<<" ";}
int col[10005];
int a[105][105];

int main() {
    int n,m,c,x;
    si(n);si(m);
    si(c);
    
    for(int i=1;i<=c;i++){
        si(x);
        col[i]=x;
    }
    
    int r=0,j=0;
    for(int i=1;i<=c;i++){
        for(int k=0;k<col[i];k++){
            a[r][j]=i;
            if(r%2==0) j++;
            else j--;
            if(j==m){
                j=m-1;
                r++;
            }
            if(j==-1){
                r++;
                j=0;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
	return 0;
}

Measured memory_bytes: 384
#define cross(a1, b1, a2, b2) ((a1)*(b2)-(a2)*(b1))
int main(){
  double a[50],b[50],s,t,x;
  int n,c=1,i;
  for(;scanf("%d",&n),n;printf("%d %.1lf\n",c,fabs(s-t)),c++){
    for(i=0;i<n;i++)scanf("%lf%lf",a+i,b+i);
    for(i=s=t=0;i<n-1;i++){
      if((x=cross(a[i],b[i],a[i+1],b[i+1]))>0)
        s+=fabs(x)/2.0;
      else
        t+=fabs(x)/2;
    }
    if((x=cross(a[i],b[i],a[0],b[0]))>0)
      s+=fabs(x)/2;
    else
      t+=fabs(x)/2;
  }
exit(0);}

Measured memory_bytes: 656
N = int(input())
A = list(map(int,input().split()))

L = list(range(1, N+1))

ZIP = zip(A, L)

ZIP = sorted(ZIP, reverse = True)

A, L = zip(*ZIP)

ans = [0] * (N + 1)

MIN = float('INF')

for i in range(N-1):
    MIN = min(MIN, L[i])
    if A[i] - A[i+1] == 0:
        continue
    ans[MIN] += (A[i] - A[i+1]) * (i + 1)
ans[1] += sum(A) - sum(ans)

for i in range(1, N+1):
    print(ans[i])

Measured memory_bytes: 31964
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  bool flag = true;
  cin >> n;
  if(n%2 != 0) {
    cout << "No" << endl;
    flag = false;
  }
  if (flag){
    string s;
    cin >> s;
    rep(i,0,n/2){
      if(s[i]!=s[i+n/2]){
        cout << "No" << endl;
        flag = false;
        break;
      }
    }
  }
  if(flag) cout << "Yes" << endl;
  return 0;
}

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


typedef long long ll;
#define reg register
#define rep(a,b,c) for(reg int a=b,a##end=c;a<=a##end;++a)
#define drep(a,b,c) for(reg int a=b,a##end=c;a>=a##end;--a)

char IO;
int rd(){
	int s=0,f=0;
	while(IO=getchar(),IO<'0'||IO>'9')if(IO=='-')f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(IO=getchar(),IO>='0'&&IO<='9');
	return f?-s:s;
}


const int N=2e3+10,K=20;

int a,b,c;



int main(){
	a=rd(),b=rd(),c=rd();
	cout<<min(c,a*b)<<endl;
}















Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
#define MAXN 200000
#define ll long long
#define rint register int
#define gc() getchar()
inline int read(rint ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
#define BUF_SIZE 1000000
#define _END fwrite(_Ob,1,_O-_Ob,stdout), _O = _Ob
#define Outc(a) (*_O++ = a)
char _Ob[BUF_SIZE+5], *_O = _Ob, _Os[25], *_Ot;
template <typename T> inline void Out(T x)
{
	if(!x){Outc('0'); return;} if(x < 0) Outc('-'), x = -x;
	for(_Ot = _Os; x; *_Ot++ = x%10+'0', x /= 10);
	for(; _Ot != _Os; Outc(*--_Ot)); if(_O-_Ob >= BUF_SIZE-50) _END;
}
int first[MAXN+5], fa[MAXN+5], sz[MAXN+5], r[MAXN+5], n, tot, cnt; ll ans[MAXN+5]; 
struct Edge{int to,nex; ll w; Edge(){} Edge(int _to, int _nex, ll _w){to=_to,nex=_nex,w=_w;}}e[MAXN+5];
inline void Add(int a, int b, ll w){e[tot] = Edge(b,first[a],w), first[a] = tot++;}
struct E{int u,v,w;}ed[MAXN+5]; inline bool operator < (E a, E b){return a.w > b.w;}
inline int getf(int x){return x-fa[x] ? fa[x] = getf(fa[x]) : x;}
void DFS(int p, ll w){ans[p] = w; for(rint u = first[p]; ~u; DFS(e[u].to,w+e[u].w), u = e[u].nex);}
int main()
{
	cnt = n = read(), memset(first+1,-1,n<<3); for(rint i = 1; i <= n; fa[i] = r[i] = i, sz[i] = 1, i++);
	for(rint i = 1; i < n; ed[i].u = read(), ed[i].v = read(), ed[i].w = read(), i++); sort(ed+1,ed+n);
	for(rint i = 1, x, y; i < n; i++)
		x = getf(ed[i].u), y = getf(ed[i].v), sz[x]>sz[y]?x^=y^=x^=y:0,
		++cnt, Add(cnt,r[x],1ll*ed[i].w*sz[y]), Add(cnt,r[y],1ll*ed[i].w*sz[x]),
		fa[x] = y, sz[y] += sz[x], r[y] = cnt;
	DFS(cnt,0); for(rint i = 1; i <= n; Out(ans[i]), Outc('\n'), i++); _END; return 0;
}

Measured memory_bytes: 15104
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
    
		// 整数の入力
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
    
		// 出力
		System.out.println(a * c < b ? c : (b - b % a) / a);
	}
}

Measured memory_bytes: 21716
#include <cstdio>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <functional>
#include <numeric>
#include <chrono>
#include <cstdlib>
using ll = long long;
using namespace std;

const ll MOD = 1e9 + 7;
const double pi = acos(-1);
#define REP(i, n) for (int(i) = 0; (i) < (n); ++(i))
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define EPS 1e-4
// bool operator<(const pair<int, int> &a, const pair<int, int> &b)
// {
//     if (a.first == b.first)
//         return a.second < b.second;
//     return a.first < b.first;
// };

/*unsigned int xor128(void)
{
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t = (x ^ (x << 11));
    x = y;
    y = z;
    z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}
unsigned int xor128rnd(unsigned int m)
{
    return xor128() % m;
}*/

bool operator<(const pair<int, int> &a, const pair<int, int> &b)
{
    if (a.first == b.first)
    {
        return a.second < b.second;
    }
    return a.first < b.first;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(8);

    int N, A, B;
    cin >> N >> A >> B;

    cout << min(A, B) << " " << max(0, A + B - N) << endl;

    return 0;
}


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

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)
#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define INF (1 << 29)

using namespace std;

int main(){
	int s, w;
	cin >> s >> w;

	if(s <= w) cout << "unsafe" << endl;
	else cout << "safe" << endl;

	return 0;
}


Measured memory_bytes: 3636
# スペース区切りの整数の入力
X,Y = map(int, input().split())

count=0
if X > 2 and Y > 2:
  count = (X-2) * (Y-2)
elif X == 1 and Y > 2:
  count = Y-2
elif Y == 1 and X > 2:
  count = X-2
elif X == 1 and Y == 1:
  count = 1

print( count )

Measured memory_bytes: 3060
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 2;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);

  int n;
  cin >> n;
  ll a[110];
  rep(i, n) cin >> a[i];
  ll Min = LINF;
  for (ll t = -100; t <= 100; t++)
  {
    ll cost = 0;
    rep(i, n)
    {
      cost += (t - a[i]) * (t - a[i]);
    }
    Min = min(Min, cost);
  }
  cout << Min << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin>>n;
	int ans=0;
	if(n==10 or n==100 or n==1000 or n==10000 or n==100000){ans=10;}
	else{
		while(n!=0){
			ans+=n%10;
			n=n/10;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;


class  Card{
	int number;
	String design;
	int value;
	public Card(int n,String d,int v) {
		// TODO Auto-generated constructor stub
		this.number=n;
		this.design=d;
		this.value=v;
	}
}


public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		Card[] A=new Card[n];
		for(int i=0;i<n;i++){
			A[i]=new Card(i, scanner.next(),scanner.nextInt());
		}
		quicksort(A,0,n-1);
		
		int i=1,j,f=1;
		while(i<n){
			j=0;
			while((f>0)&&(j<i)){
				if((A[i].value==A[j].value)&&(A[i].number<A[j].number)){
					f=0;
					System.out.println("Not stable");
				}
				j++;
			}
			i++;
		}
		if(f>0){
			System.out.println("Stable");
		}
		for(i=0;i<n;i++)
			System.out.println(A[i].design+" "+A[i].value);
	}

	private static void quicksort(Card[] A, int low, int high) {
		// TODO Auto-generated method stub
		if(low<high){
			int q=partition(A,low,high);
			quicksort(A, low, q-1);
			quicksort(A, q+1, high);
		}
	}

	private static int partition(Card[] A, int low, int high) {
		// TODO Auto-generated method stub
		int x=A[high].value;
		int i=low-1;
		for(int j=low;j<high;j++){
			if(A[j].value<=x){
				i++;
				Card m=A[i];
				A[i]=A[j];
				A[j]=m;
			}
		}
		Card m=A[i+1];
		A[i+1]=A[high];
		A[high]=m;
		return i+1;
	}

}



Measured memory_bytes: 100788
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{   
    int N,L; cin>>N>>L;
    int sum=0,Min=1e9,diff=-1;;
    for(int i=0;i<N;i++){
        sum+=L+i;
        if(abs(L+i)<Min){
            Min=abs(L+i);
            diff=L+i;
        }
    }
    cout<<sum-diff<<endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n = int(input())
pn = list(map(int, input().split()))

cnt = 1
min = pn[0]
for i in range(1, n):
    if min > pn[i]:
        cnt += 1
        min = pn[i]

print(cnt)


Measured memory_bytes: 24744
#include <stdio.h>

int main(void)
{
    int K,X,min,max,i;

    scanf("%d %d",&K,&X);

    min = X-K+1;

    max = X+K-1;

    for(i=min; i<=max; i++){
        printf("%d ",i);
    }

    printf("\n");

    return 0;
}

Measured memory_bytes: 128
n=int(input())
a=list(map(int,input().split()))
temp=[0]*n
for i in range(n):
  if a[i]%4==0:
    temp[i]=2
  elif a[i]%2==0:
    temp[i]=1
if n%2!=0 and sum(temp)>=n-1:
  print("Yes")
elif sum(temp)>=n:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; int A[110] = {}; 
	cin >> N; 
	int mx = 0; 
	for(int i = 0; i < N; i++){
		int a; cin >> a;
		mx = max(mx, a);  
		A[a] ++; 
	}
	bool possible = true; 
	for(int i = 0; i < (mx+1)/2; i++){
		if(A[i] > 0) possible = false; 
	}
	if(mx % 2 == 0){
		if(A[mx / 2] != 1) possible = false; 
		for(int i = mx / 2 + 1; i <= mx; i++){
			if(A[i] < 2) possible = false; 
		}
	}
	else if(mx % 2 == 1){
		if(A[(mx + 1) / 2] != 2) possible = false; 
		for(int i = (mx + 1) / 2; i <= mx; i++){
			if(A[i] < 2) possible = false; 
		}
	}
	if(possible) cout << "Possible" << endl; 	
	else cout << "Impossible" << endl; 
}

Measured memory_bytes: 256
n = int(input())
num = list(map(int, input().split()))
num_sort = sorted(num)
flug = 0
for i in range(n):
  if num[i] == num_sort[i]:
    continue
  else:
    flug += 1
    if flug <= 2:
      continue
    else:
      print("NO")
      exit()
print("YES")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005],h[100005];
int main() {
	int n;
	cin>>n;double s=0,a[n];
	for(int i=0;i<n;i++)
	{
	    cin>>a[i];
	}sort(a,a+n);
	s=(a[0]+a[1])/2;
	for(int i=2;i<n;i++)
	s=(s+a[i])/2;
	printf("%.5lf\n",s);
	return 0;
}

Measured memory_bytes: 256
import java.awt.*;
import java.awt.geom.*;
import java.io.*;

import java.util.*;
class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if(n == 0) break;
			int m = sc.nextInt();
			char[] s = sc.next().toCharArray();
			int count = 0;
			for (int i = 0; i < m; i++) {
				if(s[i] == 'I') {
					int len = 0;
					for (int j = 1; j + i < m; j++) {
						if (j % 2 == 1) {
							if (s[i + j] != 'O') {
								i = j + i - 1;
								len = j;
								break;
							}
						} else {
							if (s[i + j] != 'I') {
								len = j;
								i = j + i - 1;
								break;
							}
						}
						if(j + i == m-1) {
							len = j;
							i = j + i - 1;
							break;
						}
					}
					while (len >= 3 && (len-1) / 2 >= n) {
						len -= 2;
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
}

Measured memory_bytes: 32700
def main():
    from sys import stdin
    n,k = map(int,stdin.readline().rstrip().split())
    As = list(map(int,stdin.readline().rstrip().split()))
    As = [0]+As
    g = set({1})
    l = [0,1]
    now = 1
    i = 0
    while True:
        i+=1
        now = As[now]
        if now in g:
            j = l.index(now)
            print(l[j+(k-i)%(i+1-j)])
            break
            
        else:
            g.add(now)
            l.append(now)
        
        if i == k:
            print(now)
            break
main()

Measured memory_bytes: 32384
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n; cin >> n;
    vector<long> v(n);
    for(int i=0;i<n;i++)cin >> v[i];
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    long sum = 0;
    if(n%2 == 0){
        for(int i=1;i<n/2;i++){
            sum += 2*v[i];
        }
        cout << sum + v[0] << endl;
    }else{
        for(int i=1;i<(n-1)/2;i++){
            sum += 2*v[i];
        }
        cout << sum + v[0] + v[(n-1)/2] << endl;
    }
}


Measured memory_bytes: 4824
N = int(input())

ans = 0

for i in range(2, 10**6+1):
    if N % i != 0: continue
    ans += 1
    cnta = 0
    cntb = 2
    while N % i == 0:
        N //= i
        cnta += 1
        if cnta > cntb:
            cnta -= cntb
            cntb += 1
            ans += 1
    if N == 1:
        break
if N != 1:
    ans += 1


print(ans)

Measured memory_bytes: 63076
def main():
    N = int(input())
    assert N % 2 == 0
    X = list(map(int, input().split(' ')))
    Y = X.copy()
    Y.sort()
    left, right = Y[N//2-1], Y[N//2]
    for x in X:
        if x <= left:
            print(right)
        else:
            print(left)


if __name__ == '__main__':
    main()


Measured memory_bytes: 25620
import collections

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
  A, B = map(lambda x: int(x)-1, input().split())
  uf.unite(A, B)

for i in range(N):
  uf.find_root(i)
c = collections.Counter(uf.parent)
print(c.most_common()[0][1])

Measured memory_bytes: 44676
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;
import std.ascii;


void main()
{
  int a, b;
  readf("%s %s\n", &a, &b);
  max(max(a*b, a+b),a-b).writeln;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

const i64 mod = 1e9 + 7;
i64 ipow(i64 a, i64 b) {
    i64 x = a, y = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) (y *= x) %= mod;
        (x *= x) %= mod;
    }
    return y;
}
i64 inv(i64 x) {
    return ipow(x, mod - 2);
}
i64 fact(i64 x) {
    static vector<i64> f;
    i64 i = f.size();
    if (x >= i) {
        f.resize(x + 1);
        for (; i <= x; ++i) {
            f[i] = i == 0 ? 1 : i * f[i - 1] % mod;
        }
    }
    return f[x];
}
i64 perm(i64 n, i64 k) {
    return k <= n ? fact(n) * inv(fact(n - k)) % mod : 0;
}
i64 comb(i64 n, i64 k) {
    return k <= n ? fact(n) * inv(fact(k) * fact(n - k) % mod) % mod : 0;
}
int main() {
    i64 n, k;
    cin >> n >> k;
    cout << (n <= k ? 1 : 0) << endl;
    return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
 
struct UnionFind{
  vector< int > data;
  UnionFind(int sz){
    data.resize(sz, -1);
  }
  int Find(int a){
    return(data[a] < 0 ? a : data[a] = Find(data[a]));
  }
  void Union(int a, int b){
    a = Find(a), b = Find(b);
    if(a == b) return;
    if(data[a] < data[b]) swap( a, b);
    data[b] += data[a];
    data[a] = b;
  }
};
 
struct edge {
  int to, cost;
};
struct edge2 {
  int u, v, cost;
  bool operator<(const edge2& e) const {
    return cost < e.cost;
  }
};
typedef vector< vector< edge > > Graph;
typedef pair< int, int > Pi;
const int INF = 1 << 30;
int N, M, K, Q, F[100000];
Graph graph;
vector< edge2 > weighted;
set< int > buffer[100000];
int ret[100000];
 
void Dijkstra(Graph& g, vector< int >& min_cost){
  min_cost.assign( g.size(), INF);
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  for(int i = 0; i < K; i++){
    que.push( make_pair( 0, F[i]));
    min_cost[F[i]] = 0;
  }
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    if(p.first > min_cost[p.second]) continue;
    for(int i = 0; i < g[p.second].size(); i++){
      edge& e = g[p.second][i];
      if(p.first + e.cost >= min_cost[e.to]) continue;
      que.push( make_pair( p.first + e.cost, e.to));
      min_cost[e.to] = p.first + e.cost;
    }
  }
}
 
 
int main(){
  scanf("%d %d %d %d", &N, &M, &K, &Q);
  graph.resize(N);
  UnionFind uftree(N);
 
  for(int i = 0; i < M; i++){
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    --a, --b;
    graph[a].push_back((edge){b, c});
    graph[b].push_back((edge){a, c});
    weighted.push_back((edge2){a, b});
  }
 
  for(int i = 0; i < K; i++){
    scanf("%d", &F[i]);
    --F[i];
  }
  for(int i = 0; i < Q; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    --a, --b;
    buffer[a].insert(i);
    buffer[b].insert(i);
  }
 
  vector< int > min_cost;
  Dijkstra( graph, min_cost);
   
  for(int i = 0; i < M; i++){
    weighted[i].cost = min( min_cost[weighted[i].u], min_cost[weighted[i].v]);
  }
  sort( weighted.rbegin(), weighted.rend());
 
  for(int i = 0; i < M; i++){
    int u = uftree.Find(weighted[i].u), v = uftree.Find(weighted[i].v);
    if(u == v) continue;
    uftree.Union( u, v);
    int unioned = uftree.Find(weighted[i].u);
    set< int > *oo = &buffer[u], *pp = &buffer[v];
    if(u != unioned) swap( oo, pp);
    for(set< int >::iterator it = pp -> begin(); it != pp -> end(); it++){
      if(oo -> find(*it) != oo -> end()) ret[*it] = weighted[i].cost;
    }
    oo -> insert( pp -> begin(), pp -> end());
    pp -> clear();
  }
   
  for(int i = 0; i < Q; i++){
    printf("%d\n", ret[i]);
  }
}

Measured memory_bytes: 28444
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=3e5;
struct Node{int w,id;bool operator <(const Node &a)const{return w>a.w;}};
priority_queue<Node>q;
int p[N],x[N],a[N],cnt[N],n,tmp[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",x+i),p[x[i]]=i;
	for(int i=2;i<=n;i++)q.push((Node){x[i],i});
	int ti=0,tn=0;
	for(int i=1;i<=n*n;i++)
		if(p[i])
		{
			if(cnt[p[i]]!=p[i]-1){puts("No");return 0;}
			a[i]=p[i];for(int j=1;j<=n-p[i];j++)tmp[++tn]=p[i];
		}
		else
		{
			if(!q.empty())
			{
				Node t=q.top();q.pop();
				a[i]=t.id;cnt[t.id]++;
				if(cnt[t.id]!=t.id-1)q.push((Node){t.w,t.id});
			}
			else if(ti<tn)a[i]=tmp[++ti];
			else{puts("No");return 0;}
		}
	puts("Yes");
	for(int i=1;i<=n*n;i++)printf("%d ",a[i]);
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
 
#define clr(i, j)     memset(i, j, sizeof(i))
#define pb            push_back
 
typedef long long     ll;
 
//-*-*-*-*-*-*-*-*-



ll n,m,k,x,y,ans;ll a[9999999];
 vector<pair<ll,ll>>v;
 // vector<ll>v;
vector<pair<ll,ll>>vv;

int main()
{ 
 //clr(dp,0);
 /*

cin>>a>>n>>m;
for(int i=0;i<n;i++){
   cin>>x>>y;v.push_back({x,y});
}sort(v.begin(),v.end());
   for(int i=0;i<m;i++){
   cin>>x>>y;
   f[x]=min(y,f[x]);
}
for(int i=0;i<a;i++){
   nxt=v[t].first;ll o=
   if(f[i]&&i<=nxt){dp[t]=min(dp[i]+s*)}
}*/
cin>>n; ll pref[n];ans=1;
for(ll i=0;i<n;i++){
    cin>>a[i];
   if(i==0){pref[0]=a[i];}else{
  pref[i]=__gcd(a[i],pref[i-1]);}
}
ll gg=a[n-1];ll tt;ans=pref[n-1];
for(ll i=n-2;i>0;i--){
   ans=max(ans,__gcd(pref[i-1],gg));
   gg=__gcd(a[i],gg);if(i==1){tt=gg;}
}ans=max(ans,tt);if(n==2){ans=max(ans,max(a[0],a[1]));}ans=max(ans,pref[n-2]);
cout<<ans;
}





Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val words = readLine()!!.split(" ").map { it.toString() }.toMutableList()
    val a = words[0]
    val b= words[1]
    val c = words[2]

    if(a.last() == b.first() && b.last() == c.first()){
        println("YES")
    }else{
        println("NO")
    }
}

Measured memory_bytes: 36008
// AtCoder Beginner Contest 150 C.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, p_number = -1, q_number = -1, number = 1;
	
	cin >> n;
	vector<int>p(n);
	vector<int>q(n);
	vector<int>normal(n);
	for (auto& pc : p) {
		cin >> pc;
	}
	for (auto& qc : q) {
		cin >> qc;
	}


	for (int i = 0; i < n; i++) {
		normal[i] = p[i];
	}
	sort(normal.begin(), normal.end());


	do {
		if (equal(p.begin(), p.end(), normal.begin())) {
			p_number = number;
		}
		if (equal(q.begin(), q.end(), normal.begin())) {
			q_number = number;
		}


		if (p_number != -1 && q_number != -1) {
			break;
		}


		number++;
	} while (next_permutation(normal.begin(), normal.end()));


	cout << abs(p_number - q_number);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 333, mod = 1'000'000'007;
int mul(long long a, long long b){
	return a * b % mod;
}
int f[maxn][maxn][maxn], n, m;
int solve(int day, int group, int on_one){
	if(group > n) return 0;
	if(day == m) return on_one == n;
	int & v = f[day][group][on_one];
	if(~v) return v;
	v = 0;
	v += mul(solve(day + 1, group + 1, on_one), n - group);
	v += mul(solve(day + 1, group, on_one), group - on_one); if(v >= mod) v -= mod;
	v += mul(solve(day + 1, group, group), on_one); if(v >= mod) v -= mod;
	return v;
}
int main(){
	cin >> n >> m;
	memset(f, -1, sizeof(f));
	cout << solve(0, 1, 1) << endl;
	return 0;
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

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

  int N, K, C;
  cin >> N >> K >> C;
  string s;
  cin >> s;

  vector<int> L(K);
  vector<int> R(K);

  int ik = 0;
  for(int i = 0; i < N; i++){

    if(s[i] == 'o'){
      L[ik] = i;
      i = i + C;
      ik++;
    }
    if(ik==K){
      break;
    }
  }

  ik = K-1;
  for(int i = N-1; i >= 0; i--){
    if(s[i]=='o'){
      R[ik] = i;
      i = i - C;
      ik--;
    }
    if(ik == -1){
      break;
    }
  }

  vector<int> ans;
  rep(i, K){
    if(L[i] == R[i]){
      ans.push_back(L[i]+1);
    }
  }

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




  return 0;
}


Measured memory_bytes: 4236
#include<stdio.h>
#define N 2000

int main(void)
{
  int i, j, ans = 0, cnt = 0;
  char str[N][N];

  for(i = 0; i < N; i++) {
    scanf("%s", &str[i]);
    if(str[i][0] == '0') {
      break;
    }
    cnt++;
  }

  for(i = 0; i < cnt; i++) {
    for(j = 0; str[i][j] != '\0'; j++) {
      str[i][j] -= '0';
      ans += (int)str[i][j];
    }
    printf("%d\n", ans);
    ans = 0;
  }

  return 0;
}

Measured memory_bytes: 2696
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

int N, M, K, H, W, L, R;


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

	cin >> N >> M;
	vector<vector<long long int>>sum(M + 1, vector<long long int>(401));
	for (int i = 1; i <= 400; i++) {
		long long int box = 1;
		for (int j = 0; j <= M; j++) {
			sum[j][i] = box;
			box *= i;
			box %= MOD;
		}
	}
	for (int i = 0; i <= M; i++) {
		for (int j = 1; j <= 400; j++) {
			sum[i][j] += sum[i][j - 1];
			sum[i][j] %= MOD;
		}
	}
	vector<vector<long long int>>dp(N, vector<long long int>(M+1));
	vector<int>l(N);
	vector<int>r(N);
	for (auto &i : l)cin >> i;
	for (auto &i : r)cin >> i;
	for (int i = 0; i <= M; i++) {
		dp[0][i] = sum[i][r[0]] - sum[i][l[0] - 1] + MOD;
		dp[0][i] %= MOD;
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= M; j++) {
			for (int k = j; k <= M; k++) {
				dp[i][k] += dp[i - 1][j] * (sum[k - j][r[i]] - sum[k - j][l[i] - 1] + MOD);
				dp[i][k] %= MOD;
			}
		}
	}
	cout << dp.back().back() << endl;
	return 0;
}

Measured memory_bytes: 2816
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for t in T:
	left = 0
	right = n
	while left < right:
		mid = int((left + right)/2)
		if S[mid] == t:
			cnt += 1
			break
		elif t < S[mid]:
			right = mid
		else:
			left = mid + 1
		
print(cnt)
			


Measured memory_bytes: 16704
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # pragma GCC optimize "-O3"
# define int long long
using namespace std;
  
const int N = 2e3 + 7;
const int mod = 998244353;

int sum[15][N], a[15][N];

int get_sum( int x1, int y1, int x2, int y2 ) {
	int A = sum[x2][y2], D = sum[x1 - 1][y2];
	int C = sum[x2][y1 - 1], E = sum[x1 - 1][y1 - 1];
	return A - D - C + E;
}

int32_t main() {
    speed;
    int h, w, k;
    cin >> h >> w >> k;
    for ( int i = 1; i <= h; i++ ) {
    	string s;
    	cin >> s;
    	for ( int j = 0; s[j]; j++ ) {
    		a[i][j + 1] = ( s[j] == '1' );
    	}
    }
    for ( int i = 1; i <= h; i++ ) {
    	for ( int j = 1; j <= w; j++ ) {
    		sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
    	}
    }
    int ans = 1e9;
    for ( int mask = 0; mask < (1 << (h - 1)); mask++ ) {
    	vector < int > cuts = {1};
    	for ( int i = 0; i < h - 1; i++ ) {
    		if ( ( mask >> i ) & 1 ) {
    			cuts.push_back( i + 2 );
    		}
    	}
    	// cout << "-------------\n";
    	cuts.push_back( h + 1 );
    	// for ( auto i: cuts ) {
    	// 	cout << i << ' ';
    	// }
    	// cout << "\n";
    	int n = cuts.size();
    	int ok = 1, cnt = 0;
    	vector < int > vc;
    	int x = 1;
    	for ( int j = 1; j <= w; j++ ) {
    		int y2 = j;
    		int c = 0;
    		for ( int i = 0; i < n - 1; i++ ) {
    			int x1 = cuts[i], y1 = x;
    			int x2 = cuts[i + 1] - 1;
    			int S = get_sum( x1, y1, x2, y2 );
    			if ( S > k ) {
    				if ( j == 1 ) {
    					ok = 0;
    					break;
    				}
    				c = 1;
    			}
    		}
    		if ( c ) {
    			cnt++;
    			x = j;
    			vc.push_back( j );
    		}
    		if ( !ok ) {
    			break;
    		}
    	}
    	if ( !ok ) {
    		continue;
    	}
    	// for ( auto i: vc ) {
    	// 	cout << i << ' ';
    	// }
    	// cout << '\n';
    	ans = min( ans, n - 2 + cnt );
    }
    cout << ans;
}/*
111 0010 010
100 0101 110

001 1101 001
110 1000 111*/

Measured memory_bytes: 512
#include <bits/stdc++.h>
#ifdef BUG
  #include "debug.hpp"
#else
  #define DEBUG(var)
#endif

using namespace std;
template< class T1, class T2 > inline istream &
operator>>( istream & fin, pair< T1, T2 > & pr )
{ fin >> pr.first >> pr.second; return fin; }
template< class T0, class T1, class T2 > inline istream &
operator>>( istream & fin, tuple< T0, T1, T2 > & t )
{ fin >> get<0>(t) >> get<1>(t) >> get<2>(t); return fin; }
template< class T > inline istream &
operator>>( istream & fin, vector< T > & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class T, size_t n> inline istream &
operator>>( istream & fin, array<T, n> & a ) {
for(auto & u: a) fin >> u; return fin; }
template<class FwdIter> inline auto
dump(FwdIter first, FwdIter last, const char * dlm = " ") -> void {
typedef typename iterator_traits<FwdIter>::value_type value_type;
copy(first, last, ostream_iterator<value_type>(cout, dlm)); }
template<typename T> vector<T> & operator--(vector<T> & a)
{ for(auto & i: a) --i; return a; }
/* @@@ ----------------------------------- */

int main(const int argc, char **argv) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  size_t n;
  cin >> n;
  std::vector<int> a(n);
  cin >> a;
  size_t out = 0;
  int rmax = 0;

  for (const auto i: a) {
    out += rmax <= i;
    rmax = max(rmax, i);
  }
  cout << out;

  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n, k, d, sweets;
  cin >> n >> k;
  
  vector<bool> SUNUKEKUN(n);
  rep(i, k) {
    cin >> d;
    rep(j, d) {
      cin >> sweets;
      sweets--;
      SUNUKEKUN[sweets] = 1;
    }
  }
  cout << count(all(SUNUKEKUN), 0) << newl;
  return 0;
}

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

int main() {
	double r,area,length;
	cin >> r;
	area = r * r * 	3.14159265358979323846;
	length = 2 * r * 3.14159265358979323846;
	cout << fixed << setprecision(8) << area << " " << length << "\n";
	return 0;
}


Measured memory_bytes: 3288
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod 100000007

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

int main()
{
    int N;
    cin >> N;
    vector<ll> B(N);
    ll sum = 0;
    for (int i = 0; i < N - 1; i++)
    {
        cin >> B[i];
        if(i > 0){
            sum += min(B[i], B[i - 1]);
        }
        else{
            sum += B[i];
        }
    }
    sum += B[N - 2];
    cout << sum << endl;
}


Measured memory_bytes: 256
i,a[100],k,m,t;main(n){while(scanf("%d%d",&n,&m),n){for(i=0;i<n*m;scanf("%d",&t),a[i++%m]+=t);n=m;while(n--){for(t=i=0;i<m;++i)t=t<a[i]?a[k=i]:t;printf("%d%c",k+1,n?32:10),a[k]=0;}}}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
    
int main(void){
    rep(i, 5){
        int x;
        cin >> x;
        if(x != (i + 1)){
            cout << i + 1 << endl;
            break;
        }
    }
    
}


Measured memory_bytes: 3636