akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 100002;
ll n,s;
vector<ll> a;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	ll k;
	cin>>k;a.pb(k);s+=abs(k);
	FOR(i,1,n){
		cin>>k;
		a.pb(k);
		s+=abs(a[i]-a[i-1]);
	}
	s+=abs(a[n-1]);
	ll si;
	si=s;
	si-=abs(a[0]);
	si-=abs(a[0]-a[1]);
	si+=abs(a[1]);
	pri(si);
	FOR(i,1,n-1){
		si=s;
		si-=abs(a[i]-a[i-1]);
		si-=abs(a[i+1]-a[i]);
		si+=abs(a[i+1]-a[i-1]);
		pri(si);
	}
	si=s;
	si-=abs(a[n-1]);
	si-=abs(a[n-1]-a[n-2]);
	si+=abs(a[n-2]);
	pri(si);
	return 0;
}


Measured memory_bytes: 2164
n = int(input())
D_1 = [0 for i in range(n)]
D_2 = [0 for i in range(n)]
for i in range(n):
    D_1[i], D_2[i] = map(int, input().split())

tmp = 0
ans = 0
for i in range(n):
    if D_1[i] == D_2[i]:
        tmp += 1
    else:
        ans = max(tmp, ans)
        tmp = 0
ans = max(tmp, ans)

if ans >= 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9196
using System;

namespace ITP1
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            Console.WriteLine(a*b+" "+2*(a+ b));
        }
    }
}

Measured memory_bytes: 8992
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
//#define int long long

const int N=1005;
const int MOD=1e9+7;
 

int main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  /* stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
*/

  int n;
  cin>>n;
  int arr[n];
  int sum=0;
  int count=0,count1=0;
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
    sum+=arr[i];
  }
  int x=(sum+n)/n;
  int x1=sum/n;
  for(int i=0;i<n;i++)
  {
    int z=abs(x-arr[i]);
    int z1=abs(x1-arr[i]);
    z=z*z;
    z1=z1*z1;
    count+=z;
    count1+=z1;
  }
  cout<<min(count,count1);

  
    
}


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  
  int cnt = 0;
  rep(i,n){
    if(h[i]>=k) cnt++;
  }
  
  cout << cnt << endl;
}

Measured memory_bytes: 640
n, w = map(int, input().split())
W = []
V = []

for _ in range(n):
    x, y = map(int, input().split())
    W.append(x)
    V.append(y)
dp = [[0] * (w + 1) for _ in range(n + 1)]

for i in range(n):
    for sum_w in range(w + 1):
        if W[i] > sum_w:
            dp[i + 1][sum_w] = dp[i][sum_w]
        else:
            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - W[i]] + V[i])

print(dp[n][w])


Measured memory_bytes: 149936
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	H,N = inputMap()
	A = inputList()
 
	tmp = 0
	for i in A:
		tmp += i
 
	if tmp >= H:
		print("Yes")
	else:
		print("No")



if __name__ == "__main__":
	main()


Measured memory_bytes: 54128
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007
#define inf 1e18+42
#define endl "\n"

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define fori(it,A) for(auto it=A.begin();it!=A.end();it++)

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define zero(x) memset(x,0,sizeof(x));
 
using namespace std;

int binpow(int,int);
void dfs( vector< vector<int> >&, int , vector<int>& );
void bfs( vector< vector<int> >&, int , vector<int>& );

void solve()
{
    int n;
    cin>>n;

    map<string,int> p;

    rep(i,0,n)
    {
        string s;
        cin>>s;

        p[s]++;
    }

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

signed main()
{
    fast;
    int t = 1;
    // cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;
}

int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

void dfs ( vector< vector<int> > &v , int x , vector<int> &vis )
{
    vis[x] = 1;

    rep(i,0,v[x].size())
    {
        if( vis[v[x][i]] == 0 )
        {
            dfs(v,v[x][i],vis);
        }
    }
}

void bfs( vector< vector<int> > &v , int x , vector<int> &vis )
{
    queue<int> q;
    q.push(x);

    while( !q.empty() )
    {
        int p = q.front();
        q.pop();

        rep(i,0,v[p].size())
        {
            if ( vis[v[p][i]] == 0 )
            {
                vis[v[p][i]] = 1;
                q.push(v[p][i]);
            }
        }
    }
}

Measured memory_bytes: 19284
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;

int main(void){
 int max_;
 int max_second;
 int min_;
 int min_second;
 int a;
 int sum=0;
 int N;
 vector<int> A;
 vector<int> B;
 cin>>N;
 A.push_back(0);
 for(int i=0; i<N;++i){
  cin>>a; 
  A.push_back(a);
 }
 A.push_back(0);
 for(int i=1; i<A.size();++i)sum+=abs(A[i]-A[i-1]);
 for(int i=1; i<A.size()-1;++i)std::cout<<sum+abs(A[i-1]-A[i+1])-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])<<std::endl;

 return 0;
}
     
     





Measured memory_bytes: 1784
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int W,H,N;
bool A[101][101];

int main() {
  INCANT;
  cin >> W >> H >> N;
  int a,x,y;
  rep(i, N) {
    cin >> x >> y >> a;
    if (a==1) {
      rep(j, x) {
        rep(k, H) {
          A[k][j]=true;
        }
      }
    } else if (a==2) {
      rep(j, W-x) {
        rep(k, H) {
          A[k][j+x]=true;
        }
      }
    } else if (a==3) {
      rep(j, y) {
        rep(k, W) {
          A[j][k] = true;
        }
      }
    } else {
      rep(j, H-y) {
        rep(k, W) {
          A[j+y][k] = true;
        }
      }
    }
  }
  int cnt=0;
  rep(i, H) rep(j, W) cnt += !A[i][j];
  cout << cnt << "\n";
  return 0;
}

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

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ll = long long;
using P = pair<int, int>;

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cerr << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) (__VA_ARGS__)


struct UnionFind {
  vector<int> r;
  vector<int> t;
  UnionFind(int n) : r(n), t(n, 1) {
    rep(i, n) r[i] = i;
  }
  int root(int x) {
    if (x == r[x]) return x;
    return r[x] = root(r[x]);
  }
  bool same(P p) {
    return root(p.first) == root(p.second);
  }
  void add(P p) {
    int x = p.first;
    int y = p.second;
    int rx = root(x);
    int ry = root(y);
    if (rx == ry) return;
    r[ry] = rx;
    t[rx] += t[ry];
  }
  int size(int x) {
    return t[root(x)];
  }
};

void Main() {
  int n, m;
  cin >> n >> m;
  vector<P> G;
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    G.emplace_back(a, b);
  }
  reverse(G.begin(), G.end());
  vector<ll> ans(m);
  ans[0] = (ll)n*(n-1)/2;
  UnionFind uf(n);
  rep(i, m-1) {
    P p = G[i];
    ans[i+1] = ans[i];
    if (uf.same(p)) continue;
    ans[i+1] = ans[i] - uf.size(p.first) * uf.size(p.second);
    uf.add(p);
  }
  reverse(ans.begin(), ans.end());
  rep(i, m) cout << ans[i] << endl;
}

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


Measured memory_bytes: 3700
# include<stdio.h>

int main (void)
{
  int n,m,i,sum=0,t=0;
  int s[100];
  
  scanf("%d %d", &n,&m);
  
  for(i=0;i<n;i++){
    scanf("%d", &s[i]);
    sum+=s[i];
  }
  
  for(i=0;i<n;i++){
    if(s[i]>=(double)sum/(4*m))
      t++;
  }
  
  if(t>=m)
    printf("Yes\n");
  else
    printf("No\n");
  
  return 0;
  
}


Measured memory_bytes: 1620
#include <stdio.h>
int main(){
    char p[101],x[202];
    for(int i=0;i<101;i++)
        p[i]=x[i]='\0';
    int m=0,n=0;
    bool f;
    scanf("%s",x);
    scanf("%s",p);
    while(x[m]!='\0')m++;
    while(p[n]!='\0')n++;
    for(int i=m;i<m*2;i++){
        x[i]=x[i-m];
    }
    for(int i=0;i<m;i++){
        f=true;
        for(int j=0;j<n&&f;j++){
            if(p[j]!=x[j+i])f=false;
               }
               if(f){
                   printf("Yes\n");
                   return 0;
               }
               }
               printf("No\n");
               }

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

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(x, y) cerr<<#x<<": "<<bitset<y>(x) << endl;
#define line() cerr << "---------------" << endl;

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

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

int main() {
   string s;
   cin >> s;
   rep (i, s.size()) {
      if (i == 4) cout << ' ';
      cout << s[i];
   }
   cout << endl;

   return 0;
}

Measured memory_bytes: 764
n = int(input())
a = list(map(int, input().split()))
b1=[]
b2=[]
for i in range(int((n+1)/2)):
    i*=2
    b1.append(a[i])
    i+=1
    if i!=n:
        b2.append(a[i])

s = ""

if n%2==1:
    b3=b2
    b2=b1
    b1=b3
b2.reverse()

for b_ in b2:
    s+=str(b_)
    s+=" "
for b_ in b1:
    s+=str(b_)
    s+=" "
s=s.rstrip()
print(s)


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

int main(){
    int a, b, c, k, result =0;
    cin >> a >> b >> c >> k;
    while(k--){
        if(a > b and a > c){ //a maior
            a = 2*a;
        }
        else if(b > a and b > c){
            b = 2*b;
        }
        else if(c > a and c > b){
            c = 2*c;
        }
        else{
            a = 2*a;
        }
        result = a + b + c;
        
    }

    cout << result << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
int sz[N],i,n,rsz[N],a[N],x,y,fa[N];
ll z,d[N];
multiset<pair<ll,int> >s[2];
inline void ins(int u){
	if(rsz[u]==1)return;
	s[(n+d[u])&1].insert(make_pair(n+d[u]-rsz[u]*2,u));
}
bool cmp(const int&x,const int&y){return d[x]<d[y];}
inline void O(){cout<<"-1\n";exit(0);}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(i=1;i<=n;++i)cin>>d[i],a[i]=i;
	sort(a+1,a+n+1,cmp);sz[a[1]]=rsz[a[1]]=n;ins(a[1]);
	for(i=2;i<=n;++i){
		x=a[i];
		multiset<pair<ll,int> >::iterator it=s[d[x]&1].upper_bound(make_pair(d[x],0));
		if(it==s[d[x]&1].begin())O();--it;y=it->second;
		z+=rsz[x]=sz[x]=(n+d[y]-d[x])/2;rsz[y]-=sz[x];
		s[d[x]&1].erase(it);ins(y);ins(x);fa[x]=y;
	}
	if(z!=d[a[1]])O();
	for(i=1;i<=n;++i)if(fa[i])cout<<fa[i]<<' '<<i<<'\n';
	return 0;
}

Measured memory_bytes: 3712
using System.Linq;
using static System.Console;

namespace AtCoder.Probrems.Solvers.ABC118
{
    public class _C
    {
        static void Main(string[] args)
        {
            WriteLine(Solve());
        }

        public static long Solve()
        {
            ReadLine();
            return ReadLine().Split().Select(long.Parse).Aggregate(0L, (a, s) => Battle(a, s));
        }

        static long Battle(long l, long r)
        {
            return l < r ? Battle(r, l) : r != 0 ? Battle(r, l % r) : l;
        }

        private const int MOD = 1000000007;
    }
}


Measured memory_bytes: 20192
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  int a,b;

  cin >> a >> b;

  cout << a * b << endl;
  
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  int a[210];
  rep(i,n) cin >> a[i];
  bool b = true;
  int ans = 0;
  while(b) {
    rep(i,n) {
      if (a[i] % 2 != 0)  b = false; 
    }
    if(b) {
      ans++;
      rep(i,n) a[i] /= 2;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int MAX = 1 << 30;
vector<ll> a;
int calc(int div)
{
    int res = 0;
    for (int i = 0; i < a.size(); i++)
    {
        res += (a[i] + (div - 1)) / div - 1;
    }
    return res;
}
int main()
{

    ll n, k;
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int test = 2;
    int testret = calc(test);

    int left = 0;
    int right = MAX;
    while (right - left > 1)
    {
        int mid = (left + right) / 2;
        int res = calc(mid);
        if (res <= k)
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    cout << right << endl;
    return 0;
}

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

int main(){
  // input
  int N,T,A;
  cin >> N >> T >> A;
  
  // compute
  int ans;
  double best = 1e18;
  for(int i = 0; i < N; i++){
    int H;
    cin >> H;
    double diff = abs(T - H*0.006 - A);
    if(diff < best){
      best = diff;
      ans = i + 1;
    }
  }
  
  // output
  cout << ans << endl;
}

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

int main(){
	int N;
	scanf("%d", &N);
	int R[N], C[N];
	for(int i=0;i<N;i++){scanf("%d%d", &R[i], &C[i]);R[i]--;C[i]--;}
	int Rsum[N];
	for(int i=0;i<N;i++)Rsum[i]=0;
	for(int i=0;i<N;i++)Rsum[R[i]]++;
	for(int i=0;i<N;i++)if(Rsum[i]==0){printf("-1\n");return 0;}
	vector<pair<int,int> > uhyo;
	for(int i=0;i<N;i++)uhyo.push_back(make_pair(R[i], C[i]));
	sort(uhyo.begin(), uhyo.end());
	int count = 0;
	int group[N];
	for(int i=0;i<N;i++)group[i]=0;
	for(int i=0;i<N;i++)if(group[i]==0){
		count++;
		int t=i;
		while(group[t]==0){
			group[t]=count;
			t=uhyo[t].second;
		}
	}
	printf("%d\n", N-count);
	return 0;
}


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

const int maxn = 1e5+5;
int N;

struct data {
    int a,b, c;
    data(){a=0; b=0; c=0;}
    bool operator <(const data& rhs)const{
        return c>rhs.c||(c==rhs.c&&a>rhs.a)||(c==rhs.c&&a==rhs.a&&b>rhs.b);
    }
};

data d[maxn];

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    cin>>N;
    int x,y;
    for(int i = 0; i<N; i++){
        cin>>x>>y;
        d[i].a = x;
        d[i].b = y;
        d[i].c = x+y;
    }
    
    sort(d, d+N);

    
    ll ans = 0;
    for(int i = 0; i<N;i++){
        if((i&1)==0)ans+=d[i].a;
        else ans -= d[i].b;
    }
    cout<<ans<<endl;
    
    

    return 0;
}



Measured memory_bytes: 1408
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

mod = 10**9+7

n, k = map(int, input().split())
graph = [[] for _ in range(n)]
#隣接リストの作成
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)

#幅優先探索
q = deque()
seen = [False]*n
parent = [-1]*n
q.append(0)
seen[0] = True
parent[0] = 0
ret = k
while len(q)>0:
    cur = q.popleft()
    if cur == 0:
        cnt = k-1
    else:
        cnt = k-2
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            #親
            parent[i] = cur
            q.append(i)
            ret *= cnt
            ret %= mod
            cnt -= 1
print(ret)

Measured memory_bytes: 28892
from sys import exit
n, a, b = map(int, input().split())
a, b = min(a, b), max(a, b)

if (b - a) % 2 == 0:
    print((b - a) // 2)
    exit()

r = 0
to_wall_a = a - 1
to_wall_b = n - b

if to_wall_a <= to_wall_b:
    a = 1
    b -= to_wall_a
    r += to_wall_a

    b -= 1
    r += 1

    r += (b - a) // 2
else:
    b = n
    a += to_wall_b
    r += to_wall_b

    a += 1
    r += 1

    r += (b - a) // 2
print(r)

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	string s;
	cin >> s;
	bool ok = true;
	FOR(i, 0, SZ(s))
	{
		if (i & 1)
		{
			ok &= s[i] != 'R';
		}
		else
		{
			ok &= s[i] != 'L';
		}		
	}
	if (ok) cout << "Yes";
	else cout << "No";
	return 0;
}



Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rep(i, n) FOR(i, 0, n)
#define rFOR(i, a, b) for(ll i = a - 1; i >= b; i--)
#define rrep(i, a) rFOR(i, a, 0)
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<char> vc;
typedef vector<vc> vvc;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ld PI = acos(-1);
const ll INF = 1e18;
struct edge{ll to, cost;};

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

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

class SegmentTree_min{//minimum
    ll n;vl seg;
public:
    void seg_init(int n_){
        n=1;
        while(n<n_){
            n*=2;
        }
        seg.assign(2*n-1,INF);
    }
    void update(int k,ll a){
        k+=n-1;
        seg[k]=a;
        while(k>0){
            k=(k-1)/2;
            seg[k]=min(seg[2*k+1],seg[2*k+2]);
        }
    }
    ll get_min(int a,int b,int k=0,int l=0,int r=-1){//[a,b)
        if(r<0){
            return get_min(a,b,k,0,n);
        }
        if(r<=a||b<=l){
            return INF;
        }
        if(a<=l&&r<=b){
            return seg[k];
        }
        else{
            ll minl=get_min(a,b,2*k+1,l,(l+r)/2);
            ll minr=get_min(a,b,2*k+2,(l+r)/2,r);
            return min(minl,minr);
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,X;
    cin >> N >> X;
    vl A(N);
    rep(i,N){
        cin >> A[i];
    }
    SegmentTree_min st;
    st.seg_init(2*N);
    rep(t,N){
        st.update(t,A[t]);
        st.update(t+N,A[t]);
    }
    ll ans=INF;
    rep(i,N){//最大ループ
        ll res=i*X;
        rep(j,N){
            res+=st.get_min(j+N-i,j+N+1);
        }
        chmin(ans,res);
    }
    cout << ans << '\n';
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;

int main(){
  int N; cin>>N;
  vector<int> v(N);
  rep(i,N) cin>>v[i];
  sort(v.begin(),v.end());
  if(v[0]==v[N-1]){
    if(v[0]==N-1||v[0]<=N/2) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }else if(v[N-1]-v[0]==1){
    int cnt=1;
    for(int i=1;i<N;i++){
      if(v[i]==v[i-1]) cnt++;
      else break;
    }
    if(v[N-1]<=cnt+(N-cnt)/2&&v[N-1]>cnt) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
ll const MOD = 1e9 + 7;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>a[n+5];
    int ans=0;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    queue<int>sta;
    vector<int>vis(n+5,false);
    vector<int>aa;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            aa.push_back(-1);
            sta.push(i);
            aa.push_back(i);
            vis[i]=true;
            while(!sta.empty())
            {
                int  z=sta.front();
                sta.pop();
                for(auto j:a[z])
                {
                    if(vis[j]==false)
                    {
                        aa.push_back(j);
                        vis[j]=true;
                        sta.push(j);
                    }
                }
            }
        }
    }
    int x=0;
    for(int i=0;i<aa.size();i++)
    {
        if(aa[i]!=-1)x++;
        else ans=max(x,ans),x=0;
    }
    if(x)ans=max(ans,x);
    cout<<ans<<endl;
}


Measured memory_bytes: 16408
N = int(input())
A = list(map(int, input().split()))
P = 41

X = 0
for i in range(2, N):
    X ^= A[i]

S = A[0] + A[1]
A1 = A[0]

D, M = divmod(S - X, 2)
ans = -1
if M % 2 == 0 and D & X == 0 and D <= A1:
    Y = 0
    for p in range(P, -1, -1):
        if (X >> p) & 1 == 1:
            new_Y = Y ^ (1 << p)
            if D ^ new_Y <= A1:
                Y = new_Y

    ans = A1 - (D ^ Y)
    if ans == A1:
        ans = -1

print(ans)

Measured memory_bytes: 62048
N = int(input())
x = list(map(int,input().split()))
X = sorted(x)
f = 0
l = []
for p in range(X[0],X[N-1]+1):
    for i in range(N):
        f += (p-X[i])**2
    l.append(f)
    f = 0
print(min(l))

Measured memory_bytes: 3064
N = int(input())
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass
prime_l = primes(55555)
prime_l = [p for p in prime_l if p%5==1]
print(" ".join(map(str,prime_l[:N])))

Measured memory_bytes: 39536
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define distance(x1,y1,x2,y2) sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("yes");
	else say("no");
}

void Yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

void YN(bool b) {
	if (b)say("YES");
	else say("NO");
}

template<typename T>
void maxi(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T& a, T b) {
	a = min(a, b);
}

void exact_say(double x) {
	cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
}

template<class T> void getVector(vector<T>& v) {
	for (int i = 0; i < v.size(); ++i)
		cin >> v[i];
}

int main() {
	while (true) {
		makei(a);
		makes(op);
		makei(b);
		if (op == "?")break;
		else if (op == "+")cout << a + b << endl;
		else if (op == "-")cout << a - b << endl;
		else if (op == "*")cout << a * b << endl;
		else if (op == "/")cout << a / b << endl;
		else throw true;
	}
}


Measured memory_bytes: 3176
from collections import deque
from heapq import heapreplace


def get_children(ps):
    children = [set() for _ in range(n)]
    for i, p in enumerate(ps):
        children[p].add(i + 1)
    return children


def make_levels(cs):
    levels = []
    queue = deque([(0, 0)])
    while queue:
        i, l = queue.popleft()
        if fixed[i]:
            continue
        if len(levels) <= l:
            levels.append(set())
        levels[l].add(i)
        queue.extend((c, l + 1) for c in cs[i])
    return levels


def make_where():
    where = [0] * n
    for i, a in enumerate(aa):
        where[a] = i
    return where


def get_leaves(levels):
    leaves = {}
    children_count = [-1] * n
    for l, cs in reversed(list(enumerate(levels))):
        for c in cs:
            cc = children_count[c]
            pi = ps[c - 1]
            if cc == -1:
                if aa[c] == c:
                    fixed[c] = True
                    continue
                else:
                    leaves[c] = c
                if children_count[pi] == -1:
                    children_count[pi] = c
                else:
                    children_count[pi] = -2
            elif cc == -2:
                children_count[pi] = -2
            else:
                leaves[c] = cc
                if children_count[pi] == -1:
                    children_count[pi] = cc
                else:
                    children_count[pi] = -2
    return leaves


def put(i, x, where):
    # print('put', i, x)
    buf.append(i)
    where[x] = i
    x, aa[i] = aa[i], x
    while i:
        pi = ps[i - 1]
        where[x] = pi
        x, aa[pi] = aa[pi], x
        i = pi
    # assert all(i == where[aa[i]] for i in range(n))


def solve():
    cs = get_children(ps)
    # print(cs)
    while not fixed[0]:
        levels = make_levels(cs)
        leaves = get_leaves(levels)
        where = make_where()
        # print('--')
        # print(levels)
        # print(leaves)
        while leaves:
            r = aa[0]
            # print('aa', aa)
            if r in leaves:
                gci = leaves[r]
                # print('gci', r, gci, aa)
                while True:
                    a = aa[gci]
                    if not fixed[a] or a < r:
                        put(gci, r, where)
                        fixed[r] = True
                        break
                    gci = ps[gci - 1]
                del leaves[r]
            else:
                mi = max(where[i] for i in leaves if not fixed[i])
                put(mi, r, where)
        # print(aa, fixed)


n = int(input())
ps = list(map(int, input().split()))
aa = list(map(int, input().split()))
fixed = [False] * n
buf = []
solve()
print(len(buf))
print('\n'.join(map(str, buf)))


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

int main(){
int a,b,c,d,train_fee,bus_fee;

cin >> a >> b >> c >> d;

if(a < b){
train_fee = a;
}
else{
train_fee = b;
}

if(c < d){
bus_fee = c;
}
else{
bus_fee = d;
}

cout << train_fee+bus_fee << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
#define N 100
int cnt[N];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    for(int i = a; i < b; i++) {
        cnt[i]++;
    }
    for(int i = c; i < d; i++) {
        cnt[i]++;
    }
    int ans = 0;
    for(int i = 0; i < 100; i++) {
        ans += cnt[i] == 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;

int main() {
  string s;
  cin >> s;
  vector<int> ch(26);
  rep(i, s.length()) {
    ch[s[i] - 'A']++;
  }
  bool ans = true;
  rep(i, 26) {
    if(!(ch[i] == 2 || ch[i] == 0)) ans = false;
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();
   
    public void Solve() {
        var N = sc.nextInt();
        var M = sc.nextInt();
        var L = new int[M];
        var R = new int[M];
        for (int i = 0; i < M; i++) {
            L[i] = sc.nextInt();
            R[i] = sc.nextInt();
        }

        int l = L[0];
        int r = R[0];
        for (int i = 1; i < M; i++) {
            l = Math.Max(l, L[i]);
            r = Math.Min(r, R[i]);
        }
        if (r < l) {
            WriteLine(0);
        } else {
            WriteLine(r - l + 1);
        }
    }
}


class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


Measured memory_bytes: 17868
#include <iostream>

int main(){
    long long x;
    std::cin >> x;

    long long ans = x / 11 * 2, rem = x % 11;
    if(1 <= rem){
        ++ans;
    }
    if(6 < rem){
        ++ans;
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = sum(B)
for i in range(N-1):
    if A[i+1] - A[i] == 1:
        ans+=C[A[i]-1]
print(ans)


Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <bitset>
using namespace std;
#define N 200005
#define ll long long
#define mod 1000000007
int q_pow(int x,int n){int ret=1;for(;n;n>>=1,x=(ll)x*x%mod)if(n&1)ret=(ll)ret*x%mod;return ret;}
int n,A,B,C,fac[N],inv[N],ans;
int Binom(int n,int m){return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;}
void init(int M)
{
	fac[0]=1;for(int i=1;i<=M;i++)fac[i]=(ll)fac[i-1]*i%mod;
	inv[M]=q_pow(fac[M],mod-2);for(int i=M;i;i--)inv[i-1]=(ll)inv[i]*i%mod;
}
int main()
{
	scanf("%d%d%d%d",&n,&A,&B,&C);init(N-5);
	A=(ll)A*q_pow(100-C,mod-2)%mod,B=(ll)B*q_pow(100-C,mod-2)%mod;
	C=(ll)q_pow(1-(ll)C*q_pow(100,mod-2)%mod+mod,mod-3)%mod*(100-C)%mod*q_pow(100,mod-2)%mod;
	for(int i=1;i<=n;i++)
		ans=(ans+(ll)q_pow(A,n)*q_pow(B,i-1)%mod*C%mod*(i-1+n)%mod*Binom(n+i-2,i-1))%mod;
	for(int i=1;i<=n;i++)
		ans=(ans+(ll)q_pow(A,i-1)*q_pow(B,n)%mod*C%mod*(i-1+n)%mod*Binom(n+i-2,i-1))%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 1792
#include <iostream>
#include<vector>
#include<climits>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<functional>
#include <numeric>
#define FORi(N) for(int i=0;i<N;++i)
using namespace std;
using ll = long long;
ll gcd(ll m,ll n){
  if(n==0)return abs(m);
  return(gcd(n,m%n));
}
int main(){
  ll N,K;
  cin>>N>>K;
  vector<ll> X(N);
  FORi(N){
    cin>>X[i];
  }
  ll up0 = -1;
  {
    auto tmp = lower_bound(X.begin(),X.end(),0);
    up0 = distance(X.begin(),tmp);
  }
  ll min_ =LLONG_MAX;
  for(int i=max(up0-K-1,0ll);i+(K-1)<X.size()&&i<=up0;++i){
    min_ = min(min(abs(X[i+K-1]),abs(X[i]))+X[i+K-1]-X[i],min_);
  }
  cout<<min_<<endl;
  return 0;
}

Measured memory_bytes: 1024
def lotate(dic, dire):
    if dire == 'N':
        x,y,z,w = dic['up'], dic['back'], dic['bottom'], dic['front']
        dic['back'], dic['bottom'], dic['front'], dic['up'] = x,y,z,w
    elif dire == 'S':
        x, y, z, w = dic['up'], dic['back'], dic['bottom'], dic['front']
        dic['front'], dic['up'], dic['back'], dic['bottom'] = x, y, z, w
    elif dire == 'W':
        x, y, z, w = dic['up'], dic['left'], dic['bottom'], dic['right']
        dic['left'], dic['bottom'], dic['right'], dic['up'] = x, y, z, w
    elif dire == 'E':
        x, y, z, w = dic['up'], dic['left'], dic['bottom'], dic['right']
        dic['right'], dic['up'], dic['left'], dic['bottom'] = x, y, z, w
    return dic


a,b,c,d,e,f = map(int, input().split())
d = {'up':a, 'front':b, 'right':c, 'left':d, 'back':e, 'bottom':f}
s = input()
for i in s:
    d = lotate(d, i)
print(d['up'])


Measured memory_bytes: 5612
#pragma region _head

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<queue>
#include<stack>
#include<numeric>
#include<utility>
#include<regex>

#pragma region _define

#define int LL
#define f(i,a,b) for(LL i=a;i<b;i++)
#define f_vI(v,n) f(i,0,n)cin>>v[i]
#define f_v2I(v1,v2,n) f(i,0,n)cin>>v1[i]>>v2[i]
#define f_v3I(v1,v2,v3,n) f(i,0,n)cin>>v1[i]>>v2[i]>>v3[i]
#define f_vO(v,n) f(i,0,n)cout<<v[i]<<endl
#define ei else if
#define all(a) a.begin(),a.end()
#define size(s) ((LL)s.size())
#define F first
#define S second
#define check() cout<<"! ! !"
#define endl "\n"
#define _y() cout<<"Yes"<<endl
#define _Y() cout<<"YES"<<endl
#define _n() cout<<"No"<<endl
#define _N() cout<<"NO"<<endl
#define int_INF 1<<29
#define ll_INF 1LL<<60
#define MOD 1000000007

#pragma endregion

#pragma region _using

using namespace std;

using LL = long long;
using st = string;
using vi = vector<LL>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vc = vector<char>;
using vs = vector<st>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using qi = queue<LL>;
using qc = queue<char>;
using qs = queue<st>;
using si = stack<LL>;
using sc = stack<char>;
using ss = stack<st>;
using pi = pair<LL, LL>;
using mll = map<LL, LL>;
using vpi = vector<pi>;

#pragma endregion

#pragma region _graph

#define node 50  //グラフの最大位数　適宜変更
//bool graph[node][node]; bool visited[node] = { false };
#define link(a,b,m) f(i,0,m){cin>>a[i]>>b[i]; a[i]--; b[i]--; graph[a[i]][b[i]]=graph[b[i]][a[i]]=true;}

#pragma endregion

void _yn(bool p) {
	p ? _y() : _n();
}

void _YN(bool p) {
	p ? _Y() : _N();
}


LL gcd(LL a, LL b) {
	LL r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}
LL lcm(LL a, LL b) {
	return (a / gcd(a, b) * b);
}

//素数判定
bool is_prime(int n) {
	for (int i = 2; i*i <= n; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

//階乗計算
LL factorial(LL n) {
	LL a = 1, ret = 1;
	while (a < n) {
		a++;
		ret *= a;
		ret %= MOD;
	}
	return ret;
}

#pragma endregion 



/*****************************************************************************/

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

	int a, b, c;
	cin >> a >> b >> c;
	_yn(a == b && b == c);
	return 0;
}

Measured memory_bytes: 256
###
#main
if __name__ == "__main__":
    N = int(input())
    S = input()
#    count = 0
    countMin = 200001
    counttemp = 0
    isWhite = True
    numlist = []
    for t in S:
        if t == "#" and isWhite:
            isWhite = False
            numlist.append(counttemp)
            counttemp = 0
        if t == "." and not isWhite:
            isWhite = True
            numlist.append(counttemp)
            counttemp = 0
        counttemp += 1
    
    numlist.append(counttemp)
    if len(numlist) <= 2:
        countMin = 0
    else:
        countMin = sum(numlist[2::2])
        temp = countMin
        i = 2
        while i < len(numlist):
            temp += numlist[i-1] - numlist[i]
            countMin = temp if temp < countMin else countMin
            i += 2
#    print(numlist)           
    print(countMin)
    

Measured memory_bytes: 5864
n = int(input())
s = input()
s += s[0]+s[1]
lst = ["SS","SW","WS","WW"]
for x in lst:
    ans = x
    for i in range(1,n+1):
        if (s[i] == "o" and ans[i] == "S") or (s[i] == "x" and ans[i] == "W"):
            if ans[i-1] == "S": ans += "S"
            else: ans += "W"
        else:
            if ans[i-1] == "S": ans += "W"
            else: ans += "S"
    if ans[-2:] == x:
        print(ans[:n])
        exit()
print(-1)

Measured memory_bytes: 3444
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <bitset>
#include <random>
#include <stack>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <ctime>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define sc second
#define fs first
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<class T> T sqr(T x) { return x*x; }
ld pi = 3.1415926535897932384626433832795;
ll mod = 1e9 + 7;
const int N = 1e5 + 10;

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

int a[333][333], b[333][333];

int main(){
	int n;
	cin >> n;
	ll sum = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cin >> a[i][j], b[i][j] = a[i][j], sum += a[i][j];
		}
	}
	bool ok = 1;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < i; j++){
			bool deleted = 0;
			for (int k = 0; k < n; k++){
				if (k == i || k == j) continue;
				if (a[i][j] == a[i][k] + a[k][j] && !deleted)
					sum -= b[i][j] * 2, deleted = 1;
				ok &= a[i][k] + a[k][j] >= a[i][j];
			}
		}
	}
	if (!ok) cout << -1;
	else
	cout << sum / 2;
	return 0;
}

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

const int INF = 9999999;
const int MAXN = 1e5+7;

int N,M;
vector<int> vi[MAXN];
vector<int> re[MAXN];
vector<int> tpsort;
int dp[MAXN];
bitset<MAXN> ok;

void dfs(int p){
    if(ok[p])return;
    ok[p] = true;
    for(auto u : vi[p]){
        dfs(u);
    }
    tpsort.push_back(p);
}

int main(){
    cin >> N >> M;
    for(int i = 0;i <= N;++i)dp[i] = 0;
    for(int i = 0; i < M;++i){
        int x,y;
        cin >> x >> y;
        --x,--y;
        vi[x].push_back(y);
        re[y].push_back(x);
    }

    //TOPOSORT
    ok.reset();
    for(int i = 0;i < N;++i){
        if(re[i].size() == 0){
            dfs(i);
        }
    }
    reverse(tpsort.begin(),tpsort.end());

    for(auto u : tpsort){
        for(auto v : vi[u]){
            dp[v] = max(dp[v],dp[u]+1);
        }
    }
    cout << *max_element(dp,dp+N) << "\n";
}


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

int main(){
  int n, q;
  cin >> n >> q;
  stack<int> s[n];
  while(q--){
    long a, b, c;
    cin >> a >> b;
    if(!a){
      cin >> c;
      s[b].push(c);
    }
    else if(a == 1){
      if(!s[b].empty())cout << s[b].top() << endl;
    }
    else{
      if(!s[b].empty()) s[b].pop();
    }
  }
}


Measured memory_bytes: 4244
N, K = map(int, input().split())
x = list(map(int, input().split()))

ans = [0] * (N-K+1)

for i in range(N-K+1):
    l = x[i]
    r = x[i+K-1]
    ans[i] = min(abs(l)+abs(l-r), abs(r)+abs(l-r))

print(min(ans))

Measured memory_bytes: 14224
//wawando's template

#include <iostream>
#include <string>
#include <fstream>
#include <functional>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <set>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>  //clock_t , clock() , CLOCKS_PER_SEC
#include <cstring>
#include <cctype>
#include <climits> // LLONG_MAX , LLONG_MIN , INT_MAX , INT_MIN

//MACROS
#define pb              push_back
#define mp              make_pair
#define INF             1000000000     //1 billion safer for floyd warshall, avoid overflow

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

bool cmp(pair<string, int> a, pair<string, int> b) {
  if(a.first == b.first) return (a.second > b.second);
  else return (a.first < b.first);
}

int main() {
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false); cin.tie(0);

  int N;
  vector< pair<string, int> > restos, sorted;
  cin >> N;
  for(int i=0; i<N; i++) {
    string S;
    int P;
    cin >>S >>P;
    restos.pb(make_pair(S, P));
    sorted.pb(make_pair(S, P));
  }
  sort(sorted.begin(), sorted.end(), cmp);
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      if(sorted[i].first == restos[j].first && sorted[i].second == restos[j].second) {
        cout <<j+1 <<endl;
        break;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 256
S = input()

T = input()
#print(S[0:len(S)])
i = 0
flag = False
while flag == False and i <= len(S):
    #print(S[0:len(S) - i],S[len(S) - i:len(S)],T[0:i],T[0+i:len(T)])
    if S[0:len(S) - i] == T[0+i:len(T)]:
        if S[len(S) - i:len(S)] == T[0:i]:
            flag = True
            break

    i += 1

if flag == False:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3060
n = int(input())
s = input()
c = s.count('R')*s.count('G')*s.count('B')

for i in range(n):
    for j in range(i+1,n):
        if j + j - i >= n:break
        # print(j+j-i+1)
        if s[i]!=s[j] and s[j]!=s[j+j-i] and s[i]!=s[j+j-i]:
            c-=1

print(c)

Measured memory_bytes: 68188
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int calc(int[] a) {
    a.sort();

    auto n = a.length;
    auto p = n / 2;
    if (a[p-1] == a[p]) return 0;

    return a[p] - a[p - 1];
}

void main() {
    readint;
    auto a = readints;
    writeln(calc(a));
}


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

using namespace std;

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

ll N, M, Q, A, B, C, X, Y, Z;
string s, t;

vector<ll> v;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (ll i = 2; i*i <= N; ++i){
		ll x = N;
		while (x % i == 0) x /= i;
		x %= i;
		if (x == 1) Z++;
		Y = i;
	}
	//cerr << Y << ' ' << Z << '\n';
	N--;
	for (ll i = 1; i*i < N; ++i){
		if (N%i == 0){
			v.push_back(i);
			v.push_back(N/i);
		}
	}
	for (auto it : v){
		if (it > Y){
			Z++;
		}
	}
	cout << Z+1 << '\n';
}

Measured memory_bytes: 256