akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n;
  cin >> n;
 
  vector<ll> p(n);
  map<ll,ll> q;
  q[0]=1;
  
  ll sum=0;
  rep(i,n){
  cin>>p[i];
  sum+=p[i];
    if(q.count(sum)) q.at(sum)++;
    else q[sum]=1;
  }
  
  ll ans=0;
  for(auto x : q){
  ans+=x.se*(x.se-1)/2;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 14336
#include<bits/stdc++.h>
#define pb push_back
#define mod int(1e9+7)
#define N int(1e5+100)
#define pi 3.141592653589793238
#define ll unsigned long long int
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define si second
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int r;
	cin>>r;
	printf("%.5f\n",(2*pi*r));
   return 0;
}


Measured memory_bytes: 3732
#include <iostream>
#include <algorithm>
using namespace std;
int h[100];
int main(void){
    // Your code here!
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    sort(h, h + n);
    cout << h[n - 1] - h[0] << endl;
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

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

int main(int argc, char *argv[]) {
    ll l;
    cin >> l;

    cout << std::fixed << std::setprecision(12) << pow((double) l / (double) 3, 3) << endl;
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    string st;
    cin >> st;
    
    int ans = 0;
    rep(i, st.size()) ans += st[i] - '0';

    int yui = 0;
    st[0]--;
    Rep(i, st.size()) st[i] = '9';
    rep(i, st.size()) yui += st[i] - '0';

    cout << max(yui, ans) << endl;

    return 0;
}




Measured memory_bytes: 256
def c_DubiousDocument(N, S):
    from collections import defaultdict, Counter
    # 各文字列の中に共通した文字はあるか？
    d = [None for _ in range(N)]  # 文字列Siに出現する文字の一覧と個数
    for i, s in enumerate(S):
        d[i] = Counter(s)
    common = defaultdict(str)  # 文字列の中で共通する文字の一覧と個数
    for c in 'abcdefghijklmnopqrstuvwxyz':
        low = float('inf')
        for i in range(N):
            low = min(low, d[i][c])
        if low == 0:
            continue
        else:
            common[c] = low
    common = sorted(common.items())

    ans = ''
    for c, v in common:
        ans += c * v
    return ans

N = int(input())
S = [input().strip() for _ in range(N)]
print(c_DubiousDocument(N, S))

Measured memory_bytes: 3444
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int q = sc.nextInt();
		
		long shrine[] = new long[a];
		for(int i = 0; i < a; i++) {
			shrine[i] = sc.nextLong();
		}
		long temple[] = new long[b];
		for(int i = 0; i < b; i++) {
			temple[i] = sc.nextLong();
		}
		
		for(int i = 0; i < q; i++) {
			long x = sc.nextLong();
			
			int index1 = Arrays.binarySearch(shrine, x) * (-1) - 1;
			int index2 = Arrays.binarySearch(temple, x) * (-1) - 1;
			
			long shrineL = -2_000_000_000_0L;
			long shrineR = 2_000_000_000_0L;
			long templeL = -2_000_000_000_0L;
			long templeR = 2_000_000_000_0L;
			
			if(index1 >= 1) {
				shrineL = shrine[index1 - 1];
			}
			if(index2 >= 1) {
				templeL = temple[index2 - 1];
			}
			if(index1 < a) {
				shrineR = shrine[index1];
			}
			if(index2 < b) {
				templeR = temple[index2];
			}
			
//			System.out.println(index1 + " " + index2);
			
			long result = Long.MAX_VALUE;
			
			result = Math.min(result, x - Math.min(templeL, shrineL));
//			System.out.println("result1 "+result);
			result = Math.min(result, shrineR - templeL + Math.min(shrineR - x, x - templeL));
//			System.out.println("result2 "+result);
			result = Math.min(result, templeR - shrineL + Math.min(templeR - x, x - shrineL));
//			System.out.println("result3 "+result);
			result = Math.min(result, Math.max(templeR, shrineR) - x);
//			System.out.println("result4 "+result);
			
			System.out.println(result);
		}
	}
}


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

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

  for(int i = 1; i <= 9; i ++){
    if(i * 111 < n) continue;
    else{
      cout << i * 111 << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

using ll = long long;
using namespace std;

int main() {
    int p, q, r;
    cin >> p >> q >> r;
    cout << std::min({ p + q,q + r,r + p }) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct memo{int sy,sx,gy,gx;};

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int h,w; cin>>h>>w;
	vector<vector<int>>a(h,vector<int>(w));
	for(auto&&i:a){
		for(auto&&j:i){
			cin>>j;
		}
	}
	vector<memo>ans;
	for(int i=0;i<h;++i){
		for(int j=0;j<w;++j){
			if(a.at(i).at(j)%2==0)continue;
			if(j+1<w){
				--a.at(i).at(j),++a.at(i).at(j+1);
				ans.push_back({i+1,j+1,i+1,j+2});
			}
			else if(i+1<h){
				--a.at(i).at(j),++a.at(i+1).at(j);
				ans.push_back({i+1,j+1,i+2,j+1});
			}
		}
	}
	cout<<ans.size()<<"\n"s;
	for(auto&&i:ans)cout<<i.sy<<" "s<<i.sx<<" "s<<i.gy<<" "s<<i.gx<<"\n"s;
}


Measured memory_bytes: 6328
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define CST(x) cout<<fixed<<setprecision(x)
#define PI 3.14159265359
#define MOD 1000000007
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
///1<<3シフト演算子 とは　0001の1を三つずらして1000にする, これは8を表しておりつまりbitは0から7まで
//条件式 ? 真の場合の文 : 偽の場合の文
//string S  S,at(i),S += T,S += c,S.size(),S.substr(l)l文字目から最後まで,
///S.substr(l, r)l文字目からl+r-1文字目 n文字目から0個で空列を返せる
//*min_element(all(x)) *max_element(all(x))
//vi x; x.back(),x.front(),x.push_back(),x.pop_back()
//gcd(a, b)最大公約数
//sort(all(x)),reverse(all(x)),sort(x.begin()+l,a.begin()+r)lからrまで
//stack<int> a; a.push(x),a.pop(),a.top(),a.empty()bool
//queue<int> b; b.push(x),b.pop(),b.front(),b.empty()bool,b.size() 要素が小さい順
//priority_queue<int, vector<int>, greater<int>> c,c.top()
//map<int, int> M1; 変数[key] = value; 変数.erase(key); 変数.at(key); 変数.count(key)所属判定　変数.size()
//find(all(x), key)boolソート済みのベクトル
//*lower_bound(all(x),k)以上の最小の要素,*uppper_bound(all(x),k)より大きい最小の要素
//char('0'+cnt) 数字cntからcharへの変換
//int(char-'0') charからintへの変換
//binary_search(all(p),x) bool型




int main(){

    int n,m; cin >> n >> m;
    vector<pair<ll,ll>> v;
    rep(i,n){
        int a; cin >> a;
        v.push_back({a,1});
    }
    rep(i,m){
        int b,c; cin >> b >> c;
        v.push_back({c,b});
    }
    sort(all(v),greater<pair<ll,ll>>());
    ll num = 0;
    ll res = 0;
    for(auto p : v){
        if(num + p.second <= n){
            res += p.first * p.second;
            num += p.second;
        }
        else{
            res += p.first * (n - num);
            num = n;
            break;
        }

    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 6384
import java.util.*;
 
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String a = sc.next();
    String b = sc.next();
    String n = a+b;
    int k = Integer.parseInt(n);
    int kk = (int)(Math.sqrt(k));//平方数を返す
    //System.out.println(kk);
    System.out.println(Math.pow(kk, 2) == k ? "Yes" : "No");
  }
}
    
    

Measured memory_bytes: 39004
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
#include <array>

using namespace std;

int main(){
  string s;
  char ans;
  cin >> s;
  int N = s.size();
  int i;
  int num[30]={0};

  for (i = 0; i < N; i++)
    num[s.at(i) - 'a'] ++;
  bool find = false;
  for (i = 0; i <= 'z'-'a'; i++){
    if (num[i] == 0){
      find = true;
      break;
    }
  }
  ans = 'a' + i;
  if (find)
    cout << ans << endl;
  else
    cout << "None";
  return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    double r;
    cin >> r;
    printf("%.6f %.6f\n", M_PI * r * r, 2 * M_PI * r);
}

Measured memory_bytes: 1232
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n, m, p; cin>>n>>m>>p;
    vector<vector<P>> G(n);
    for(int i=0; i<m; i++){
        int a, b, c; cin>>a>>b>>c;
        a--, b--;
        G[a].emplace_back(b, p - c);
    }

    vector<ll> dist(n, INF);
    dist[0] = 0;
    for(int i=0; i<2*n; i++){
        for(int j=0; j<n; j++){
            for(auto nxt : G[j]){
                int nv, cost;
                tie(nv, cost) = nxt;

                if(dist[j] != INF && dist[nv] > dist[j] + cost){
                    dist[nv] = dist[j] + cost;
                    if(i >= n) dist[nv] = -INF;
                }
            }
        }
    }

    if(dist[n-1] == -INF) cout << -1 << endl;
    else cout << max(0LL, -dist[n-1]) << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    string s; cin >> s;
    for(int i = 0; i < s.size(); i++) cout << (char) ((((s[i] - 'A') + n) % 26) + 'A');

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String sr = sc.nextLine();//文字列入力
		char[] ch = sr.toCharArray();//文字単位でリスト化
		for (int i = 0; i < ch.length; ++i) {//繰り返し
			if (Character.isUpperCase(ch[i])) {//大文字か判断
				ch[i] = Character.toLowerCase(ch[i]);//上の判定で大文字なら小文字にする
			} else {
				ch[i] = Character.toUpperCase(ch[i]);//違うのなら大文字にする
			}
		}
		StringBuffer sb = new StringBuffer(new String(ch));//StringBufferからStringへキャスト
		System.out.println(sb.toString());//出力時に文字列に変換

	}

}



Measured memory_bytes: 26076
#include<stdio.h>
int main(){
  int nzin[101][101],kosuu,rinsetu,count,i,arr,j,num,k;
  scanf("%d",&num);
  for(i=1;i<=num;i++){
    scanf("%d",&nzin[i][1]);/*ばんごう*/
    scanf("%d",&nzin[i][2]);/*こすう*/
      for(j=0;j<nzin[i][2];j++){
	scanf("%d",&nzin[i][3+j]);
      }
  }
  for(k=1;k<=num;k++)/*行*/{
    for(i=1;i<num;i++)/*1からつながる最大数まで調べる*/{
      count=0;
      for(j=0;j<nzin[k][2];j++)/*隣接している数だけ回す*/{
	if(nzin[i][1]==nzin[k][3+j])
	  count++;
      }
      printf("%d ",count);
    }
    i=num;
    count=0;
    for(j=0;j<nzin[k][2];j++){
      if(nzin[i][1]==nzin[k][3+j])
	count++;
    }
    printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 636
s = int(input())

def cmb(n, r):#コンビネーション(mod)の高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
N = 10000 #Nの最大値
g1 = [0]*(N+1) #元テーブル(p(n,r))
g1[0] = g1[1] = 1
g2 = [0]*(N+1) #逆元テーブル
g2[0] = g2[1] = 1
inverse = [0]*(N+1) #逆元テーブル計算用テーブル
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod

d = s % 3
n = s // 3
ans = 0
for i in range(1,n+1):
    ans += cmb(d+3*(n-i)+i-1, d+3*(n-i))
    ans %= mod
print(ans)

Measured memory_bytes: 65380
class Solve:
    def __init__(self):
        tmp = [int(i) for i in input().split()]
        if len(tmp) == 1:
            self.cal = False
        else:
            self.cal = True
            q1, b, c1, c2, q2 = tmp

            self.B = b
            self.C = (c1, c2)
            self.Q = (q1, q2)

            self.a = 0  # >= 0; True;
            self.b = min(self.Q[1]+1, self.B//self.C[0]+1)  # <= 10**6+1; False

    def check(self, A):
        b = self.B
        b -= self.C[0] * A  # self.b(??????)?????????????´\?¶????100A[g]????????\??¶?????????????????????
        b -= self.C[1] * max(0, self.Q[0]-A)
        if b >= 0:
            return True
        else:
            return False

    def solve(self):
        while self.b - self.a > 1:
            m = (self.a + self.b) // 2
            if self.check(m):
                self.a = m
            else:
                self.b = m
        return self.buy(self.a)

    def buy(self, A):
        if A == 0:
            return ['NA']
        else:
            return [str(A), str((self.B-self.C[0]*A)//self.C[1])]

while True:
    s = Solve()
    if not s.cal:
        break

    print(" ".join(s.solve()))

Measured memory_bytes: 7688
#include <stdio.h>

int main()
{

    int i, j, n, m;
    int a[1000][100];
    int b[100];
    int c[1000];

    scanf("%d %d", &n, &m);

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            scanf("%d", &a[i][j]);
        }
    }

    for(i=0;i<m;i++){
        scanf("%d", &b[i]);
    }

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            c[i] += b[j] * a[i][j]; 
        }
    }

    for(i=0;i<n;i++){
       printf("%d\n", c[i]);
    }
    return 0;
}

Measured memory_bytes: 644
#include <iostream>
#include <stack>

using namespace std;

int H,W;
int c[1402][1402];
int h[1402][1402];

void prepare() {
  for (int i = 1; i <= H; ++i) {
    for (int j = 1; j <= W; ++j) {
      h[i][j] = (c[i][j] + h[i-1][j])*c[i][j];
    }
  }
}

int solve_sub(int i) {
  int ans = 0;
  int last_j;
  stack<pair<int, int>> s;
  pair<int, int> tmp;
  for (int j = 1; j <= W+1; ++j) {
    if (s.empty() || (s.top().second < h[i][j])) {
      s.push(make_pair(j, h[i][j]));
    }
    else {
      while (!s.empty() && s.top().second >= h[i][j]) {
        last_j = s.top().first;
        ans = max(ans, (j-last_j)*(s.top().second));
        s.pop();
      }
      s.push(make_pair(last_j, h[i][j]));
    }
  }
  return ans;
}

int solve() {
  int ans = 0;
  for (int i = 1; i <= H; ++i) {
    ans = max(ans, solve_sub(i));
  }
  return ans;
}

int main () {
  cin>>H>>W;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      cin>>c[i+1][j+1];
      c[i+1][j+1] ^= 1;
    }
  }
  prepare();
  cout<<solve()<<endl;
}



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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    ll r;
    cin>> r;

    cout<< 3 * r* r;
    nl;

    return 0;
}




Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 998244353;
const int N = 2e5 + 10;

int p[11][N], n;
int t[4*N], lazy[4*N];

void build(int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = p[10][n - tl];
	} else {
		int tm = (tl + tr) / 2;
		build(v*2, tl, tm);
		build(v*2+1, tm+1, tr);
		t[v] = (t[v*2] + t[v*2+1]) % mod;
	}
}

void push(int v, int tl, int tm, int tr) {
	if(lazy[v] != inf) {
		t[v*2] = p[lazy[v]][tm - tl + 1] * p[10][n - tm] % mod;
		lazy[v*2] = lazy[v];
		t[v*2+1] = p[lazy[v]][tr - (tm + 1) + 1] * p[10][n - tr] % mod;
		lazy[v*2+1] = lazy[v];
		lazy[v] = inf;
	}
}

void update(int v, int tl, int tr, int l, int r, int x) {
	if (l > r) 
		return;
	if (l == tl && tr == r) {
		t[v] = p[x][r - l + 1] * p[10][n - r] % mod;
		lazy[v] = x;
	} else {
		int tm = (tl + tr) / 2;
		push(v, tl, tm, tr);
		update(v*2, tl, tm, l, min(r, tm), x);
		update(v*2+1, tm+1, tr, max(l, tm+1), r, x);
		t[v] = (t[v*2] + t[v*2+1]) % mod;
	}
}

int query(int v, int tl, int tr, int l, int r) {
	if (l > r)
		return 0;
	if (l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) / 2;
	push(v, tl, tm, tr);
	return ((query(v*2, tl, tm, l, min(r, tm)) + query(v*2+1, tm+1, tr, max(l, tm+1), r)) % mod);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int q;
	cin >> n >> q;
	for(int i = 1; i <= 9; i++) {
		p[i][0] = 0;
		for(int j = 1; j <= n; j++) {
			p[i][j] = (p[i][j - 1] * 10LL + i) % mod;
		}
	}
	p[10][0] = 1;
	for(int i = 1; i <= n; i++) {
		p[10][i] = (p[10][i - 1] * 10LL) % mod;
	}
	build(1, 1, n);
	for(int i = 0; i < 4*N; i++) {
		lazy[i] = inf;
	}
	while(q--) {
		int l, r, d;
		cin >> l >> r >> d;
		update(1, 1, n, l, r, d);
		cout << t[1] << endl;
	}

	return 0;
}

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

using namespace std;
static const int MAX = 10;

int factorial(int n) {
    int f = 1;
    for (int i = 1; i <= n; ++i) f *= i;
    return f;
}

double distance(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return pow(dx * dx + dy * dy, 0.5);
}

int main() {
    int N, X[MAX], Y[MAX], R[MAX];
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
        cin >> Y[i];
        R[i] = i;
    }

    double D[MAX][MAX];
    for (int i = 0; i < N - 1; ++i) {
        for (int j = i + 1; j < N; ++j) {
            // i - j 間距離 (i > j)
            double d = distance(X[i], Y[i], X[j], Y[j]);
            D[i][j] = d;
        }
    }

    double sum = 0;
    int f = factorial(N);
    for (int i = 0; i < f; ++i) {
        int prev = R[0];
        for (int j = 1; j < N; ++j) {
            sum += D[min(prev, R[j])][max(prev, R[j])];
        }
        next_permutation(R, R + N);
    }

    cout.precision(10);
    cout << sum / f << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
//#include<string>
using namespace std;
int main() {
	int n,k,x,s=0;
	cin >>n>>k;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (x < k - x) {
			s += 2*x;
		}
		else {
			s += 2 * (k - x);
		}
	}
	
	cout << s << endl;
	
	//system("pause");
}

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

using namespace std;

const int MAXN = 1e6;
int x;
bool visit[MAXN];

int eto() {
	for (int i = 2; i < MAXN; i++) {
		if (visit[i]) {
			for (int j = i + i; j < MAXN; j += i) {
				visit[j] = false;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	memset(visit, true, sizeof(visit));

	eto();

	cin >> x;


	for (int i = x; i < MAXN; i++) {
		if (visit[i]) {
			cout << i << "\n";
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false)
#define ll  long long
int pr[400000], vs[400000];
vector<int>v[300000];
queue<int>q;
int main()
{
    IO;
    int i, j, n, m, m2, k, t,a1,a2, l, th, h, r, mx, x, y;
    cin>>n>>m; r=n;
    for(i=1; i<=m; i++){
        cin>>j>>k;
        v[j].push_back(k);
        v[k].push_back(j);
    }
    q.push(1);
    while(!q.empty())
    {
        n = q.front(); q.pop();
        for(i=0; i<v[n].size(); i++){
            if(!vs[v[n][i]]){
                vs[v[n][i]]=1; pr[v[n][i]]=n;
                q.push(v[n][i]);
            }
        }
    }
    cout<<"Yes"<<endl;
    for(i=2; i<=r; i++) cout<<pr[i]<<endl;
    return 0;
}


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

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

  vector<int> H(N);
  for(int i=0; i<N; i++) cin >> H[i];

  if(N<=K) {
    puts("0");
    return 0;
  }

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

  int sum = 0;
  for(int i=0; i<N-K; i++) sum += H[i];
  cout << sum << endl;
}


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

int main()
{
    long long n, m;
    cin >> n >> m;
    //偶数の近傍が存在するマスしか裏のカードは存在しない

    if (n < 2 && m >= 2)
    {
        m -= 2;
    }
    else if (m < 2 && n >= 2)
    {
        n -= 2;
    }
    else
    {
        n -= 2;
        m -= 2;
    }

    cout << n * m << endl;

    return 0;
}


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

#define F first
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 310, M = 1010;

int n, m, k, d;
int g[N][N];
PII p[N * N];

int main()
{
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
		{
			scanf("%d", &g[i][j]);
			p[g[i][j]] = {i, j};
		}
	p[0] = p[d];
		
	vector<vector<LL>> s(d + 10);
	for (int i = 0; i < d; i ++ )
	{
		s[i].resize((n * m + d - 1) / d + 10);
		s[i][0] = 0;
		for (int j = 0; i + (j + 1) * d <= n * m; j ++ )
		{
			int l = j * d + i, r = (j + 1) * d + i;
			// if (i == 2) cout << l << ' ' << r << endl;
			LL x1 = p[l].F, y1 = p[l].S;
			LL x2 = p[r].F, y2 = p[r].S;
			LL sum = abs(x1 - x2) + abs(y1 - y2);
			
			s[i][j + 1] = s[i][j] + sum;
		}
	}
		
	scanf("%d", &k);
	while (k -- )
	{
		int l, r;
		scanf("%d%d", &l, &r);
		
		if (l == r) puts("0");
		else
		{
			int t = l % d;
			printf("%lld\n", s[t][r / d] - s[t][l / d]);
		}
	}
	return 0;
}

Measured memory_bytes: 12032
#include <iostream>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;

int main() {
  char c; cin >> c;
  int n = c - 'A';
  char res;
  if(n<26) res = 'A';
  else res = 'a';
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3592
const val INF = Int.MAX_VALUE / 4

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  if (n == 1) {
    println("POSSIBLE")
    return
  }

  val graph = Array(n, { mutableListOf<Int>() })
  val rawParents = readLine()!!.split(" ").map(String::toInt)
  rawParents.forEachIndexed { rawIndex, rawValue ->
    val index = rawIndex + 1
    val parent = rawValue - 1
    graph[parent].add(index)
  }
  val xs = readLine()!!.split(" ").map(String::toInt)

  val dp = IntArray(n, { INF })
  fun isValid(v: Int): Boolean {
    if (graph[v].size == 0) {
      dp[v] = 0
      return true
    }
    if (graph[v].any { !isValid(it) }) {
      return false
    }

    val innerDP = Array(graph[v].size + 1, { IntArray(xs[v] + 1, { INF }) })
    innerDP[0].fill(0)
    for (i in graph[v].indices) {
      val c = graph[v][i]
      val v1 = xs[c]
      val v2 = dp[c]
      for (k1 in 0..xs[v]) {
        if (innerDP[i][k1] < INF) {
          if (k1 + v1 <= xs[v]) {
            innerDP[i + 1][k1 + v1] = Math.min(innerDP[i + 1][k1 + v1], innerDP[i][k1] + v2)
          }
          if (k1 + v2 <= xs[v]) {
            innerDP[i + 1][k1 + v2] = Math.min(innerDP[i + 1][k1 + v2], innerDP[i][k1] + v1)
          }
        }
      }
    }
    val min = innerDP[graph[v].size][xs[v]]
    if (min == INF) return false
    dp[v] = min
    return true
  }

  val ans = isValid(0)
  println(if (ans) "POSSIBLE" else "IMPOSSIBLE")
}


Measured memory_bytes: 46788
# coding: utf-8
line = input().split()
n = int(line[0])
m = int(line[1])
l = int(line[2])
a = [[0 for i in range(m)] for j in range(n)]
b = [[0 for i in range(l)] for j in range(m)]
c = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
    line = input().split()
    for j in range(m):
        a[i][j] = int(line[j])

for i in range(m):
    line = input().split()
    for j in range(l):
        b[i][j] = int(line[j])

for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j] += a[i][k]*b[k][j]
        if j < l - 1:
            print(str(c[i][j]), end=" ")
        else:
            print(str(c[i][j]))


Measured memory_bytes: 7024
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

x = ni()
ans = 0
ans += (x // 500) * 1000
x -=(x // 500) * 500
ans += (x // 5) * 5
print(ans)


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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> h(n,0);
    for(int i=0;i<n;i++){
        cin >> h[i];
    }

    sort(h.begin(),h.end());
    int diff = 1000000000;
    for(int i=0;i+k-1<n;i++){
        diff = min(diff,h[i+k-1]-h[i]);
    }

    cout << diff << endl;
}



Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()

	dp := make([]int, n+1)
	for i := 1; i <= n; i++ {
		dp[i] = n
	}
	for i := 1; i <= n; i++ {
		for pow := 1; pow <= i; pow *= 6 {
			dp[i] = min(dp[i], dp[i-pow]+1)
		}
		for pow := 1; pow <= i; pow *= 9 {
			dp[i] = min(dp[i], dp[i-pow]+1)
		}
	}

	puts(dp[n])
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;

#define sp << " " <<
#define mod 1000000007
#define PI 3.14159265358979323
#define y second
#define x first
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define pqueue priority_queue< ll >
//#define pdqueue priority_queue< ll,vector<ll> ,greater< ll > >
#define codejamDebug(x) cout<<"Case #"<<x<<": ";
#define debug(x) cout<<#x<<" :"<<x<<endl;
#define rep(i,n) for(long long i=0;i<n;i++)
#define f(i,a,b) for(long long i = a; i < b; i++)
#define fd(i,a,b) for(long long i = a; i >=b; i--)
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int           ll;
typedef long double             ld;
typedef unsigned long long int ull;
typedef vector <int>            vi;
typedef vector <ll>            vll;
typedef pair <int, int>        pii;
typedef pair <ll, ll>          pll;
typedef vector < pii >        vpii;
typedef vector < pll >        vpll;
typedef vector <string>         vs;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

//Handle:cyber_rajat

int main(int argc, char const *argv[])
{
	sync;
	ll n;
	cin >> n;
	for (int a = -150; a <= 150; a++){
		for (int b = -150; b <= a; b++){
			if (pow(a, 5) - pow(b, 5) == n){
				cout << a << " " << b;
				return 0;
			}
		}
	}
	return 0;
}


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

char int2char(int x){
  char card[4]={'S','H','C','D'};
  return card[x];
}

int char2int(char c){
  int i;
  char card[4]={'S','H','C','D'};
  
  for(i=0;i<4;i++){
    if(c==card[i]){
      return i;
    }
  }
}

int main(){
  int i,j,c,n,x;
  int card[4][13];

  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      card[i][j]=0;
    }
  }

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf(" %c %d",&c,&x);
    card[char2int(c)][x-1] = 1;
  }

  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      if(card[i][j]==0){
	printf("%c %d\n",int2char(i),j+1);
      }
    }
  }
  
  return 0;
}

Measured memory_bytes: 596
# coding=utf-8
from collections import deque
n = int(input())
deque = deque()
input_lines = [input().split() for x in range(n)]

for i in range(n):
    inp = input_lines[i]
    if inp[0] == 'insert':
        deque.appendleft(inp[1])
    elif inp[0] == 'deleteFirst':
        deque.popleft()
    elif inp[0] == 'deleteLast':
        deque.pop()
    else:
        if inp[1] in deque:
            deque.remove(inp[1])

print(*deque)

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

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

int main(){
    ll n; cin >> n;
    ll x, y;
    vector<pair<ll, ll>> vp;
    pair<ll, ll> p;
    map<pair<ll, ll>, ll> mp;
    for (ll i = 0; i < n; i++)
    {
        cin >> x >> y;
        p = make_pair(x, y);
        vp.push_back(p);
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++)
    {
        pair<ll, ll> start = vp[i];
        for (ll j = 0; j < n; j++)
        {
            if(i == j) continue;
            p = make_pair(vp[j].first - start.first, vp[j].second - start.second);
            if(mp[p]) mp[p]++;
            else mp[p] = 1;
            ans = max(ans, mp[p]);
        }
    }
    cout << n - ans << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<cmath>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main(){
char a[5]={'\0'};
fgets(a,5,stdin);
if (strlen(a)==4){
	for (int i=0;i<3;i++)
		cout<<a[2-i];
}else{
	cout<<a[0]<<a[1];
}

	return 0;
}

Measured memory_bytes: 256
n = raw_input()
l = len(n)

ans = 0

t = 2**(l-1)

if l == 1:
	print n
	quit()

for i in range(t):
	bit = (bin(i)[2:]).zfill(l-1)
	formula = ''

	p = 0
	b = 0

	while b < len(bit):
		formula += n[p]
		formula += "+" if bit[b] == "1" else ""
		p += 1
		b += 1

	formula += n[-1]
	ans += eval(formula)

print ans

Measured memory_bytes: 2692
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str1[] = br.readLine().split("");
		String str2[] = br.readLine().split("");

		int max = 0;
		for (int i = 0; i < str1.length - str2.length + 1; i++) {
			int count = 0;
			for (int j = 0; j < str2.length; j++) {
				if (str1[i + j].equals(str2[j])) {
					count++;
				}
			}
			max = Math.max(count, max);
		}

		System.out.println(str2.length - max);
	}

}

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

int main(){
  int n;
  cin>>n;
  int a[100];
  int h=0;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(abs(a[i])>abs(a[h])) h = i;
  }

  cout<<2*n -1<<endl;

  for(int i=0;i<n;i++)
    cout<<h+1<<" " <<i+1<<endl;

  if(a[h]>0){
    for(int i=0;i<n-1;i++)
      cout<<i+1<<" "<<i+2<<endl;
  }
  else{
    for(int i=n;i>1;i--)
      cout<<i<<" "<<i-1<<endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
vector<vi> graph;
vector<int> ans;

int main()
{
	int n, m, x, y, i;
	scanf("%d %d", &n, &m);
	graph.assign(n + 1, vi());
	ans.assign(n + 1, 0);
	for (i = 0; i < m; ++i)
	{
		scanf("%d %d", &x, &y);
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	queue<int> q;
	q.push(1);
	ans[1] = -1;
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int i = 0; i < graph[x].size(); ++i)
		{
			if (ans[graph[x][i]] == 0)
			{
				ans[graph[x][i]] = x;
				q.push(graph[x][i]);
			}
		}
	}

	for (i = 1; i <= n; ++i)
	{
		if (ans[i] == 0)
		{
			printf("-1");
			return 0;
		}
	}
	printf("Yes\n");
	for (i = 2; i <= n; ++i) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 10268
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

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

const ll mod = 1000000007;

struct Corr{
  ll y;
  ll x;
  ll depth;
};
vector<string> vec;
queue<Corr> q;
vector<int> x_vec = {0, 0, +1, -1};
vector<int> y_vec = {+1, -1, 0, 0};

ll h, w; //height, width
ll s_y, s_x, g_y, g_x; //Start, Goal
ll y, x, depth; //現在位置
map<ll, ll> depth_cnt;

ll bfs(){
  while (!q.empty()){
    Corr now = q.front(); q.pop();
    y = now.y, x = now.x, depth = now.depth;
    if (y == g_y && x == g_x) return depth;
    depth_cnt[now.depth]++;
    for (ll i = 0; i < 4; ++i){
      Corr next = {y + y_vec[i], x + x_vec[i], depth + 1};
      if (0 <= next.y && next.y <= h - 1 && 0 <= next.x && next.x <= w - 1 && vec[next.y][next.x] == '.'){
        vec[next.y][next.x] = 'x';
        q.push(next);
      }
    }
  }
  depth_cnt[0] = 0;
  return 0;
}

int main(){
  cin >> h >> w;
  s_y = 0; s_x = 0; g_y = h - 1; g_x = w - 1;
  vec.resize(h);
  rep(i, h) cin >> vec[i];
  Corr start = {s_y, s_x, 0};
  q.push(start); vec[0][0] = 'x';

  ll res = 0;
  rep (i, h){
    rep(j, w){
      if (vec[i][j] == '.') res++;
    }
  }

  int de = bfs();
  res -= de;
  if (de == 0) cout << -1 << endl;
  else cout << res << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define bg begin()
#define ed end()
#define fi first()
#define se second()
using namespace std;
using ll = long long;
using vint = vector<int>;
using pint = pair<int,int>;
using vpint = vector<pint>;
template <typename T>
T sq(T x){
  return x * x;
}
ll mod = 1e9 + 7;

signed main (){
  int N;
  cin >> N;
  cout << "ABC" << N << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

using namespace std;

#ifdef LOCAL
static struct __timestamper {
  string what;
  __timestamper(const char* what) : what(what){};
  __timestamper(const string& what) : what(what){};
  ~__timestamper(){
    TIMESTAMPf("%s", what.data());
	}
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;

const int MOD = 998244353;

void add(int &a, int b) {
  if ((a += b) >= MOD)
    a -= MOD;
}

void sub(int &a, int b) {
  if ((a -= b) < 0)
    a += MOD;
}

int mul(int a, int b) { return (int)((a * 1LL * b) % MOD); }

int mpow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)
      res = mul(res, a);
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

int minv(int x) { return mpow(x, MOD - 2); }

int mex(vector<int> a) {
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  a.push_back(1e9);
  int res = 0;
  while (a[res] == res) res++;
  return res;
}

vector<int> readGraph(int n) {
  vector<vector<int>> g(n);
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    if (a < b) {
      g[a].push_back(b);
    } else {
      g[b].push_back(a);
    }
  }

  vector<int> id(n);
  for (int i = n - 1; i >= 0; i--) {
    vector<int> nxt;
    nxt.reserve(g[i].size());
    for (int v : g[i]) {
      nxt.push_back(id[v]);
    }
    id[i] = mex(nxt);
  }

  vector<int> score(*max_element(id.begin(), id.end()) + 1);
  int v = ll(1e18) % MOD;
  int cur = v;
  for (int i = 0; i < n; i++) {
    add(score[id[i]], cur);
    cur = mul(cur, v);
  }
  return score;
}

int main() {
#ifdef LOCAL
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);
#endif

  int n;
  while (scanf("%d", &n) == 1) {
    vector<int> g1 = readGraph(n);
    vector<int> g2 = readGraph(n);
    vector<int> g3 = readGraph(n);

    auto get = [](const vector<int>&a, int pos) {
      if (pos < (int)a.size()) return a[pos];
      return 0;
    };

    int ans = 0;
    for (int i = 0; i < (int)g1.size(); i++) {
      for (int j = 0; j < (int)g2.size(); j++) {
        int cur = mul(g1[i], g2[j]);
        cur = mul(cur, get(g3, i ^ j));
        add(ans, cur);
      }
    }
    printf("%d\n", ans);
  }


  return 0;
}


Measured memory_bytes: 4816
#include <bits/stdc++.h>
#include <ctime>
#include <cstdlib>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define swap(a, b) (a += b, b = a - b, a -= b)
using namespace std;
int main()
{
    int a;
    string s;
    cin >> a >> s;
    if (a >= 3200)
    {
        cout << s << endl;
    }
    else
    {
        cout << "red" << endl;
    }
}

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

static int
ll_cmp ( const void *a, const void *b ) {
    long long *a_ = (long long*)a;
    long long *b_ = (long long*)b;
    if ( *a_ > *b_ )
        return 1;
    else if ( *a_ < *b_ )
        return -1;
    return 0;
}

int main (void) {
    int n_tree, n_deco;
    int i;
    scanf("%d%d", &n_tree, &n_deco);
    long long tree_h[n_tree];
    for ( i=0; i<n_tree; i++ )
        scanf("%lld", &tree_h[i]);

    long long diff, diff_min=LLONG_MAX;
    qsort(tree_h, n_tree, sizeof(long long), ll_cmp);
    for ( i=0; i<=n_tree-n_deco; i++ ) {
        diff = tree_h[i+n_deco-1] - tree_h[i];
        if ( diff < diff_min )
            diff_min = diff;
    }

    printf("%lld\n", diff_min);
    return EXIT_SUCCESS;
}


Measured memory_bytes: 1788
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <cmath>
#include <random>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK make_pair
#define PB push_back
#define VI vector<int>
#define VII vector<int,int>
#define MSI map<string,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define W1 while(1);
const int MOD = 1000000007;
int main()
{
	char a, b;
	cin >> a >> b;
	if ((a == 'H'&&b == 'H') || (a == 'D'&&b == 'D'))
	{
		cout << 'H' << endl;
	}
	else
	{
		cout << 'D' << endl;
	}
	return 0;
}

Measured memory_bytes: 256
/*input

*/


// assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;

// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll          long long int
#define pb          push_back
#define pii         pair<ll ,ll >
#define vpii        vector< pii >
#define vi          vector<ll >
#define vs			vector< string >
#define vvi         vector< vector< ll > >
#define inf			(ll)1e18
#define all(it,a)   for(auto it=(a).begin();it!=(a).end();it++) 
#define F           first
#define S           second
#define sz(x)       (ll )x.size()
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repr(i,a,b) for(ll  i=a;i>b;i--)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define whatis(x)   cout << #x << " is " << x << "\n";
#define graph(n)    adj(n,vector< ll > () )
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define debug(x)     cout << #x << " " << x << endl;
#define debug_p(x)   cout << #x << " " << x.F << " " << x.S << endl;
#define debug_v(x)   {cout << #x << " "; for (auto ioi : x) cout << ioi << " "; cout << endl;}
#define debug_vp(x)  {cout << #x << " "; for (auto ioi : x) cout << '[' << ioi.F << " " << ioi.S << ']'; cout << endl;}
#define debug_v_v(x) {cout << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cout << ioi2 << " "; cout << '\n';} cout << "*/" << #x << endl;}
const ll N = 1e5+5;
vvi adj(N,vi ());
vi ans(N,-1);
ll n,m;
void dik()
{
	priority_queue<pii,vpii,greater<pii>> q;
	vi dist(n,inf);
	dist[0]=0;
	q.push(mp(dist[0],0));
	map<ll,ll> par;
	while(!q.empty())
	{
		ll cur = q.top().S;
		ll d   = q.top().F;

		q.pop();

		rep(i,0,sz(adj[cur]))
		{
			ll ch = adj[cur][i];
			ll nd = d+1;
			if(nd<dist[ch])
			{
				dist[ch]=nd;
				par[ch]=cur;
				q.push(mp(dist[ch],ch));
			}
		}
	}

	// debug_v(dist);
	rep(i,1,n) ans[i]=par[i];



}

int solve()
{
	cin>>n>>m;
	rep(i,0,m)
	{
		ll x,y;
		cin>>x>>y;
		x--,y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}

	dik();

	ll w=1;
	rep(i,1,n) if(ans[i]==-1) w=0;
	if(w)
	{
		cout<<"Yes\n";
		rep(i,1,n) cout<<ans[i]+1<<"\n";
	} 
	else cout<<"No\n";

	return 0;
}

int main()
{
	auto start = chrono::high_resolution_clock::now();

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

	ll test_cases=1;
	//cin>>test_cases;
	while(test_cases--)
		solve();

	auto stop = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::milliseconds>(stop-start);
	//cout<<"\nduration: "<<(double)duration.count()<<" milliseconds";
}

Measured memory_bytes: 20668
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij=[(1,0),(0,1),(-1,0),(0,-1)]

def dfs(i,j):
    cnt=[0]*2
    color=ss[i][j]
    ss[i][j]=2
    cnt[color]+=1
    for di,dj in dij:
        ni,nj=i+di,j+dj
        if ni<0 or ni>=h or nj<0 or nj>=w:continue
        if ss[ni][nj]!=1-color:continue
        ret=dfs(ni,nj)
        cnt[0]+=ret[0]
        cnt[1] += ret[1]
    return cnt

h,w=MI()
ss=[[c=="#" for c in SI()] for _ in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if ss[i][j]==2:continue
        black,white=dfs(i,j)
        #print(i,j,black,white)
        ans+=black*white
print(ans)


Measured memory_bytes: 180324
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k=sc.nextInt();
		if(k==1){
			System.out.println(0);
		}else{
			System.out.println(n-k);
		}
	}
}


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

#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 ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 100100;

int A[MAX];

LL S[MAX];
LL DP[MAX];

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

	int n;
	scanf("%d", &n);

	FOR (i, 0, n)
	{
		scanf("%d", &A[i]);
	}

	sort(A, A+n);

	FOR (i, 0, n)
	{
		S[i] = A[i];
		if (i) S[i] += S[i-1];
	}

	int res = 0;

	DP[n] = 0;
	RFOR(i, n, 0)
	{
		LL cur = S[i];

		if (cur >= DP[i+1]) res++;

		LL val = A[i];
		DP[i] = max(DP[i+1] - val, (val + 1) / 2);
	}

	cout<<res<<endl;


}


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

int main()
{
    int N, K, x, a, b;
    int ans = 0;
    cin >> N >> K;

    for (int i = 0; i < N; i++)
    {
        cin >> x;
        //パターンA
        a = x * 2;
        //パターンB
        b = (K - x);
        if (b < 0)
        {
            b *= -1;
        }
        b = b * 2;
        
        if (a < b)
        {
            ans += a;
        }
        else
        {
            ans += b;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636