akhauriyash/Code-Regression huggingface dataset:
(defun b (x1 y1 x2 y2)
  (let ((x3 (- x2 (- y2 y1)))
	(x4 (- x1 (- y2 y1)))
	(y3 (+ y2 (- x2 x1)))
	(y4 (+ y1 (- x2 x1))))
    (list x3 y3 x4 y4)))

(defun split (line)
  (let ((result ()) (str ""))
    (dolist (i (loop for i across line collect i))
      (if (eql i #\space)
	  (progn
	    (setf result (append result (list (parse-integer str))))
	    (setf str ""))
	  (setf str (concatenate 'string str (string i)))))
    (setf result (append result (list (parse-integer str))))
    result))

(format t "~{~a ~}" (eval `(b ,@(split (read-line)))))


Measured memory_bytes: 6248
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  string S;
  cin >> S;
  vector<bool> is_found(26, false);
  for (int i = 0; i < S.length(); i++) {
    is_found[S[i] - 'a'] = true;
  }
  vector<char> availables;
  for (int i = 0; i < 26; i++) {
    if (!is_found[i]) availables.push_back(i + 'a');
  }
  string ans = "-1";
  if (S.length() < 26) {
    ans = S + availables[0];
    cout << ans << endl;
    return 0;
  }
  for (int i = S.length() - 1; i >= 0; i--) {
    char replace_char = -1;
    for (int j = 0; j < availables.size(); j++) {
      if (S[i] < availables[j]) {
        replace_char = availables[j];
        break;
      }
    }
    if (replace_char != -1) {
      ans = S.substr(0, i);
      ans += replace_char;
      break;
    } else {
      availables.push_back(S[i]);
      sort(availables.begin(), availables.end());
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8

code = list(map(int, input().split(" ")))

M = code[1]
C = code[2]

B = list(map(int, input().split(" ")))


ans = 0

for i in range(code[0]):
    tC = 0
    A = list(map(int, input().split(" ")))

    for j in range(M):
        tC = tC + B[j] * A[j]

    if 0 < tC + C:
        ans = ans + 1

print(ans)

Measured memory_bytes: 3064
#include <iostream>

using namespace std;

int sx, sy, tx, ty;

void solve() {
  string s = "";

  for (int i = 0; i < tx-sx; i++) { s += 'R'; }
  for (int i = 0; i < ty-sy; i++) { s += 'U'; }
  for (int i = 0; i < tx-sx; i++) { s += 'L'; }
  for (int i = 0; i < ty-sy; i++) { s += 'D'; }

  s += 'D';
  for (int i = 0; i < tx-sx+1; i++) { s += 'R'; }
  for (int i = 0; i < ty-sy+1; i++) { s += 'U'; }
  s += 'L';
  s += 'U';
  for (int i = 0; i < tx-sx+1; i++) { s += 'L'; }
  for (int i = 0; i < ty-sy+1; i++) { s += 'D'; }
  s += 'R';

  cout << s << endl;
}

int main() {
  cin >> sx >> sy >> tx >> ty;
  solve();
}

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

const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main(){
    double a, b, x;
    cin >> a >> b >> x;
    double s = x / a, rad = 0.0;
    if (s <= a*b/2.0) {
        double w = s / b * 2.0;
        rad = atan2(b, w);
    }
    else {
        double h = (a * b - s) / a * 2.0;
        rad = atan2(h, a);
    }
    double ans = rad / PI * 180.0;
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 4076
def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

m,n=map(int,input().split())

mod=10**9+7

print(power(m,n))



Measured memory_bytes: 5600
S = input()

def f(S):
    if S.startswith('A'):
        if S[2:-1].count('C') == 1:
            hantei = S[1] + S[2:-2].replace('C', 'c') + S[-1]
            if hantei.islower():
                return 'AC'
    return 'WA'

print(f(S))

Measured memory_bytes: 3060
use std::io::*;
// hは最終的に0未満になってる可能性があることに注意!

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let h: usize = itr.next().unwrap().parse().unwrap();
    let w: usize = itr.next().unwrap().parse().unwrap();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut a: Vec<usize> = (0..n)
        .map(|_| itr.next().unwrap().parse().unwrap())
        .collect();

    let mut ans: Vec<Vec<usize>> = vec![vec![0; w]; h];
    let mut idx = 0;

    for i in 0..h {
        if i % 2 == 0 {
            for j in 0..w {
                ans[i][j] = idx + 1;
                a[idx] -= 1;
                if a[idx] == 0 {
                    idx += 1;
                }
            }
        } else {
            for j in (0..w).rev() {
                ans[i][j] = idx + 1;
                a[idx] -= 1;
                if a[idx] == 0 {
                    idx += 1;
                }
            }
        }
    }
    let mut out = Vec::new();

    for i in 0..h {
        for j in 0..w - 1 {
            write!(out, "{} ", ans[i][j]).ok();
        }
        writeln!(out, "{}", ans[i][w - 1]).ok();
    }
    stdout().write_all(&out).unwrap();
}


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

int main()
{
    int N, Q;
    cin >> N >> Q;
    dsu d(N);
    rep(_, Q) {
        int t, u, v;
        cin >> t >> u >> v;
        if (t == 0) {
            d.merge(u, v);
        } else if (t == 1) {
            if (d.same(u, v)) {
                cout << "1" << '\n';
            } else {
                cout << "0" << '\n';
            }
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3928
package main

import "fmt"

func main() {
	var A, B int
	fmt.Scan(&A, &B)
	if 0 < A {
		fmt.Println("Positive")
	} else if A <= 0 && 0 <= B {
		fmt.Println("Zero")
	} else {
		if abs(B-A+1)%2 == 0 {
			fmt.Println("Positive")
		} else {
			fmt.Println("Negative")
		}
	}
}

func abs(a int) int {
	if a < 0 {
		a *= -1
	}
	return a
}


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

int main(void){
  int N;//数列の長さ
  int x;
  cin>>N;

  int data[N]={0};
 
  for(int i=0;i<N;i++){
    cin>>x;
    data[i]=x;
  }

  for(int i=0;i<N-1;i++){
    cout<<data[i]<<" ";
  }
  cout<<data[N-1];
  cout<<endl;

  for(int i=1;i<=N-1;i++){
    int v=data[i];
    int j=i-1;

    while(j>=0 && data[j]>v){
      data[j+1]=data[j];
      j--;
    }
    data[j+1]=v;
    
    for(int i=0;i<N-1;i++){
      cout<<data[i]<<" ";
    }
    cout<<data[N-1];
    cout<<endl;
  } 
 
  return 0;
}



Measured memory_bytes: 3116
a = [list(map(int, input().split())) for _ in range(3)]
n = int(input())
b = [int(input()) for _ in range(n)]
for i in b:
    for j in range(3):
        for k in range(3):
            if i == a[j][k]:
                a[j][k] = 0
for i in range(3):
    if a[i][0] == a[i][1] == a[i][2] == 0:
        print('Yes')
        break
else: 
    for i in range(3):
        if a[0][i] == a[1][i] == a[2][i] == 0:
            print('Yes')
            break
    else:
        if a[0][0] == a[1][1] == a[2][2] == 0:
            print('Yes')
        elif a[2][0] == a[1][1] == a[0][2] == 0:
            print('Yes')
        else: print('No')

Measured memory_bytes: 3188
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val dictionary = mutableSetOf<String>()
    repeat(n) {
        val (command, s) = readLine()!!.split(' ')
        when (command) {
            "insert" -> dictionary.add(s)
            "find" -> println(if (dictionary.contains(s)) "yes" else "no")
        }
    }
}


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

bool isFull(bool array[], const int SIZE) {
  for(int i = 0; i < SIZE; i++) {
    if(array[i] == false) {
      return false;
    }
  }

  return true;
}

int main(int argc, char const *argv[]) {
  const int SIZE = 16;
  bool array[SIZE] = {};
  int two[] = {0, 0};

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

  // int index = 0;
  // bool flag = false;
  // while(true) {
  //   if(two[0] == A && two[1] == B) {
  //     flag = true;
  //     break;
  //   }
  //
  //   if( isFull(array, SIZE) ) {
  //     break;
  //   }
  //
  //   array[index % 16] = true;
  //   two[index % 2]++;
  //   index++;
  // }

  if(A <= SIZE / 2 && B <= SIZE / 2) {
    cout << "Yay!\n";
  } else {
    cout << ":(\n";
  }

  return 0;
}


Measured memory_bytes: 256
d = int(input())
c = list(map(int,input().split()))
s = [0]*d
for i in range(d):
    s[i] = list(map(int,input().split()))
lis = [0]*26
sum_score = 0
for i in range(d): #d日全てに対して
    ans = -float("Inf")
    num = 0
    for j in range(26): #i日目にj番目を選んだ時の得点を計算
        score = 0
        score += s[i][j]
        for k in range(26):
            if k != j:
                score -= (lis[k]+1)*c[k]
        if score > ans:
            ans = score
            num = j
    sum_score += ans
    #print(sum_score)
    print(num+1)
    for j in range(26):
        if j != num:
            lis[j] += 1
        else:
            lis[j] = 0
    #print(lis)

Measured memory_bytes: 9296
import math, sys

S = input()
n = len(S)
if n == 1:
    print(int(S))
    sys.exit()
ans = 0
for i in range(2**(n-1)):

    ib = (bin(i)[2:]).zfill(n-1)
    #print(ib)

    l = 0
    for j in range(n):
        if j == n-1:
            ans += int( S[l:j+1] )
            #print( S[l:j+1] , ans)
            break
        if ib[j] =="1":
            ans += int( S[l:j+1] )
            #print( S[l:j+1] , ans)
            l = j+1
print(ans)

Measured memory_bytes: 68416
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 998244353
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=300050;
//ここまでテンプレ
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}
int main(){
	//%MOD下での階乗
	ll ex[SIZE]={1,0};
	for(int i=1;i<SIZE;i++){
		ex[i]=ex[i-1]*i%MOD;
	}
	//%MOD下での階乗の逆数
	ll inv[SIZE]={1,0};
	for(int i=1;i<SIZE;i++){
		inv[i]=mod_pow(i,MOD-2,MOD);
	}
	for(int i=1;i<SIZE;i++){
		inv[i]=inv[i-1]*inv[i]%MOD;
	}
	ll N,A,B,K;
	cin>>N>>A>>B>>K;
	ll ans=0;
	for(int i=0;i<=N;i++){
		if(A*i>K)
			continue;
		//Bを何個ぬればいい？
		if((K-A*i)%B!=0)
			continue;
		ll j=(K-A*i)/B;
		if(j>N)
			continue;
		//Aをiこ塗るとおり数
		/*
		ll temp=combination_mod(N,i,MOD);
		temp*=combination_mod(N,j,MOD);
		*/
		ll tempA=ex[N]*inv[i]%MOD*inv[N-i]%MOD;
		ll tempB=ex[N]*inv[j]%MOD*inv[N-j]%MOD;
		ans+=tempA*tempB%MOD;
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<limits>
#include<bitset>
#include<functional>
#include<type_traits>
#include<queue>
#include<stack>
#include<array>
#include<random>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>


using namespace std;

using ll = long long int;
using lln = long long unsigned;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const double PI = acos(-1.0);
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define all(v) v.begin(), v.end()
const long MOD = pow(10, 9) + 7;

char alfa[] = { 'A','B' ,'C','D' ,'E' ,'F' ,'G' ,'H' ,'I' ,'J' ,'K' ,'L' ,'M' ,'N' ,'O' ,'P' ,'Q' ,'R' ,'S' ,'T' ,'U' ,'V' ,'W' ,'X' ,'Y','Z' };

inline void finish() {
	cout << -1 << endl;
	exit(0);
}

unsigned GetDigit(double num) {
	return log10(num) + 1;
}

ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

class Mod {
public:
	static inline ll Add(ll a, ll b) {
		return (a + b) % MOD;
	}

	static inline ll Sub(ll a, ll b) {
		ll ans = (a - b) % MOD;
		return (ans < 0) ? (ans + MOD) : ans;
	}

	static inline ll Mul(ll a, ll b) {
		return (a * b) % MOD;
	}

	static inline ll Div(ll a, ll b) {
		return (a % MOD) * modinv(b, MOD) % MOD;
	}
};



template <typename T>
inline void debug(vector<T> v) {
	cout << "[";
	for (ll i = 0; i < v.size() - 1; ++i) {
		cout << v[i] << ", ";
	}
	cout << v[v.size() - 1] << "]" << endl;
}

void Main();
inline void DebugMain() {
	while (true) {
		Main();
	}
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);

	bool debug = false;
	if (debug) {
		cout << "\x1b[41m" << "Debug Mode " << endl;
	}
	(debug) ? DebugMain() : Main();
	return 0;
}

class man
{
public:
	int A;
	vector<pii> X;
	bool HeIsTrue;
private:

};

inline void Main() {
	ll X, Y, N;
	vector<ll> A;
	ll M1, D1, M2, D2;
	ll ans;
	ll sum = 0, count = 0,a =0;
	string S;
	string T;
	string Ans = "";
	int b[60];
	bool flag = false;

	cin >> N>>X;

	Yes(X <= N * 500);
}



Measured memory_bytes: 256
import java.util.Scanner;



public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] array = new int[6 + 1];
		array[0] = 0;
		for (int i = 1; i < array.length; i++) {
			array[i] = scan.nextInt();
		}
		int q = scan.nextInt();
		Dice dice = new Dice(array);
		int part1; int part2;
		for (int i = 0; i < q; i++) {
			part1 = scan.nextInt();
			part2 = scan.nextInt();
			System.out.println(dice.check(part1, part2));
		}
		scan.close();
	}
}
	

class Dice {
	private int[] num = new int[6 + 1];
	Dice() {
	}

	Dice(int[] array) {
		for (int i = 0; i < array.length; i++) {
			this.num[i] = array[i];
		}
	}
	
	public int[] getNum() {
		return this.num;
	}
	
	public int getNumber(int i) {
		return this.num[i];
	}
	
	// ??????????????¢??????????????????
	public int[] roll(String order) {
		int now_1 = 1;	int now_2 = 2;	int now_3 = 3;	int tmp;
		int[] array = getNum();
		char[] check = {'N', 'E', 'S', 'W'};
		for (int i = 0; i < order.length(); i++) {
			for (int j = 0; j < check.length; j++) {
				if (order.charAt(i) == check[j]) {
					switch (j + 1) {
						case 1:
							tmp = now_1;
							now_1 = now_2;
							now_2 = 7 - tmp;
							break;
						case 2:
							tmp = now_1;
							now_1 = 7 - now_3;
							now_3 = tmp;
							break;
						case 3:
							tmp = now_1;
							now_1 = 7 - now_2;
							now_2 = tmp;
							break;
						case 4:
							tmp = now_1;
							now_1 = now_3;
							now_3 = 7 - tmp;
							break;
					}
				}
			}
		}
		int[] cp_array = new int[array.length];
		cp_array[1] = array[now_1]; cp_array[2] = array[now_2];
		cp_array[3] = array[now_3]; cp_array[4] = array[7 - now_3];
		cp_array[5] = array[7 - now_2]; cp_array[6] = array[7 -now_1];
		return cp_array;
	}
	
	public int[] turn(int[] array) {
		int tmp;
		tmp = array[2];
		array[2] = array[3];
		array[3] = array[5];
		array[5] = array[4];
		array[4] = tmp;
		
		return array;
	}
	
	public int check(int part1, int part2) {
		String[] str = {"null", "N", "NN", "S", "W", "E"};
		int sum = 0;
		int[] array = new int[num.length];
		for (int i = 0; i < num.length; i++) {
			array[i] = num[i];
		}
		boolean decision = false;
		for (int i = 0; i < str.length; i++) {
			array = this.roll(str[i]);
			for (int j = 0; j < 4; j++) {
				if (array[1] == part1)
					if (array[2] == part2) {
						sum = array[3];
						decision = true;
						break;
					} else {
						array = this.turn(array);
					}
			}
			if (decision) break;
		}
		

		return sum;
	}
	
	public void print(int[] array) {
		for (int i = 1; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}
}

Measured memory_bytes: 26360
use std::io::{self, Read};

fn main() {
    let mut buffer = String::new();
    io::stdin().read_to_string(&mut buffer).unwrap();
    let mut iter = buffer.split_whitespace();

    for i in 1..(10000 + 1) {
        let n: u16 = iter.next().unwrap().parse().unwrap();
        if n == 0 {
            break;
        }
        println!("Case {}: {}", i, n);
    }
}



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

int main() {
    int n;
    cin >> n;
    int a[n], b[n], c[n-1];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n-1; i++) cin >> c[i];

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += b[a[i]-1];
        if (i != n-1 && a[i] != n && a[i+1] == a[i]+1) {
            ans += c[a[i]-1];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3556
s = list(input())
n = int(input())
right_lst = ["0"]*(2*10**5)
left_lst = ["0"]*(2*10**5)
S = left_lst + s + right_lst
left = 2*10**5
right = 2*10**5+len(s)-1
isReverse=False
#print(left,right)
for i in range(n):
  A = input().split(" ")
  if A[0]=="1":
    isReverse = not isReverse
    #print(S[left:right+1])
    #print(left,right)
    continue
  else:
    if (A[1]=="1" and isReverse) or (A[1]=="2" and not isReverse):
      right +=1
      S[right] = A[2]
      
    else:
      left-=1
      S[left] = A[2]
      
    #print(S[left:right+1])
    #print(left,right)

ans = S[left:right+1] 
#print(ans)    
if isReverse:
  ans = list(reversed(ans))

a = "".join(ans)
print(a)
      
  
    

Measured memory_bytes: 15564
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>

using namespace std;

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

const ll MOD = ll(1e9 + 7);
const ll INF = LLONG_MAX;
const ll MAX_N = ll(1e3) + 5;
const double EPS = 10e-8;
const double PI = 3.14159265359;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)

int main() {
    string s,ans="";
    cin >> s;
    for(int i=0;i<s.size();i+=2){
        ans += s[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1e18;
ll fac[MAX], finv[MAX], inv[MAX];
//ダイクストラ法は負の経路があるとき使えない→ベルマンフォード法
int main(){
  ll v,e,s,t;cin>>v>>e>>s>>t;
  s--;t--;
  vector<vp> iki(v),kaeri(v);vll ikidis(v,MOD),kaeridis(v,MOD);
  
  rep(i,0,e){
    ll x,y,a,b;cin>>x>>y>>a>>b;
    
    x--;y--;
    iki[x].push_back(make_pair(y,a));
    iki[y].push_back(make_pair(x,a));
    kaeri[x].push_back(make_pair(y,b));
    kaeri[y].push_back(make_pair(x,b));
  }
  priority_queue<P,vector<P>,greater<P> > pq;
  ikidis[s]=0;
  pq.push(make_pair(ikidis[s],s));
  while(!pq.empty()){
    P p=pq.top();
    pq.pop();
    ll from=p.second;
    if(ikidis[from]<p.first)continue;
    for(auto &edge:iki[from]){
      if(ikidis[edge.first]>ikidis[from]+edge.second){
        ikidis[edge.first]=ikidis[from]+edge.second;
        
        pq.push(make_pair(ikidis[edge.first],edge.first));
      }
    }
  }
  
  kaeridis[t]=0;
  pq.push(make_pair(kaeridis[t],t));
  while(!pq.empty()){
    P p=pq.top();
    pq.pop();
    ll from=p.second;
    if(kaeridis[from]<p.first)continue;
    for(auto &edge:kaeri[from]){
      if(kaeridis[edge.first]>kaeridis[from]+edge.second){
        kaeridis[edge.first]=kaeridis[from]+edge.second;
        
        pq.push(make_pair(kaeridis[edge.first],edge.first));
      }
    }
  }
  
  priority_queue<P> pq2;
  rep(i,0,v){
    pq2.push(make_pair(1e15-ikidis[i]-kaeridis[i],i));
  }
  rep(i,0,v){
    while(pq2.top().second<i)pq2.pop();
    cout<<pq2.top().first<<endl;
  }
  
}




Measured memory_bytes: 20340
import java.util.*

fun main(args: Array<String>) {
    val (n, q) = readLine()!!.split(' ').map { it.toInt() }

    val g = mutableMapOf<Int, MutableList<Int>>()
    repeat(n - 1) {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        g.getOrPut(a) { mutableListOf() }.add(b)
        g.getOrPut(b) { mutableListOf() }.add(a)
    }

    val cnt = IntArray(n + 1)
    repeat(q) {
        val (p, x) = readLine()!!.split(' ').map { it.toInt() }
        cnt[p] += x
    }

    val visited = BooleanArray(n + 1) { false }
    val stack = ArrayDeque<Int>()
    stack.addLast(1)
    visited[1] = true

    while (stack.isNotEmpty()) {
        val v = stack.removeLast()
        for (u in g[v]!!) {
            if (visited[u]) continue
            cnt[u] = cnt[v] + cnt[u]
            stack.addLast(u)
            visited[u] = true
        }
    }

    println(cnt.slice(1..n).joinToString(" "))
}


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


int n,m,T;
int d,t,s;
int main()
{
	cin >> d >> t >> s;
	double ans = d*1.0/s;
	if(ans <= t*1.0)
	cout << "Yes"<<endl;
	else cout << "No"<<endl;
	return 0;
}

Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        char[] s = Console.ReadLine().ToCharArray();
        int k = int.Parse(Console.ReadLine());

        for (int i = 0; i < s.Length; i++)
        {
            if (i == s.Length - 1)
            {
                char newChar = (char)((s[i] - 97 + (k % 26)) % 26 + 97);
                s[i] = newChar;
                
            }
            else if (s[i] == 'a')
            {
                continue;
            }
            else
            {
                int num = 26 - (s[i] - 97);
                if (num <= k)
                {
                    k -= num;
                    s[i] = 'a';
                }
            }
        }

        Console.WriteLine(s);
    }

}


Measured memory_bytes: 13304
//C++14 (Clang 3.8.0)

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=100011;
ll comb(ll a,ll b){
  ll res=1LL;
  for(ll i=a;i>(max(b,a-b));i--) res*=i;
  for(ll i=1LL;i<=min(b,a-b);i++) res/=i;
  return res;
}
int main(){
  int n;
  cin>>n;
  ll a[maxn];
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n);
  ll cent=(a[n-1]-1LL)/2LL+1LL;
  ll minn=a[n-1];
  int minind=-1;
  for(int i=0;i<n;i++){
    if (abs(a[i]-cent)<minn){
      minn=abs(a[i]-cent);
      minind=i;
    }
  }
  cout<<a[n-1]<<" "<<a[minind]<<endl;

}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>

using namespace std;
#define REP(i,m,n) for(int i=m;i<n;++i)
#define INF 10000000000000000
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define all(v) v.begin(),v.end()

vector<int>v;

int main() {
	int n, h;
	cin >> n >> h;
	int d = -1;
	REP(i, 0, n) {
		int a, b;
		cin >> a >> b;
		v.push_back(b);
		d = max(a, d);
	}
	sort(all(v));
	int ans = 0;
	REP(i, 0, n) {
		if (v[n - i - 1] <= d)break;
		h -= v[n - i - 1];
		ans++;
		if (h <= 0) {
			printf("%d\n", ans);
			return 0;
		}
	}
	ans += (h + d - 1) / d;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 892
N, X = map(int, input().split())
L = [int(x) for x in input().split()]
D = []
i = 0
while N+1:
  if i == 0:
    D.append(0)
  elif i<=N:
    D.append(D[i-1]+L[i-1])
  else:
    break
  i+=1
print(len([int(y) for y in D if int(y)<=X]))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int MOD = 1e9+7;
int main() {
    IO;
    int n ;
    cin>>n ;
    vector<int>primes (1e6+2 , -1 );
    for(ll i = 2 ; i<1e6 ; i++){
        if(primes[i]==-1){
            for(ll j = i*i ; j <1e6+2 ; j+=i){
                primes[j]=i;
            }
        }
    }

    vector<int>vec(n);
    unordered_set<int>sing ;
    bool found =false;
    for(int  i = 0 ;i <n ; i++ ){
        cin>>vec[i];

        int num = vec[i];
        unordered_set<int>last;
        while (!found&&primes[num]!=-1){
            if(last.count(primes[num])){
                num/=primes[num];
                continue;
            }
            if(sing.count(primes[num])){
                found=true;
                break;
            }
            sing.insert(primes[num]);
            last.insert(primes[num]);
            num/=primes[num];
        }
        if(num!=1){
            if(!last.count(num)&&sing.count(num)){
                found=true;
            }
            sing.insert(num);
        }

    }
    if(!found){
        cout<<"pairwise coprime" <<endl;
        return 0;
    }
    int num = vec[0];
    for(int i = 1 ; i<n ; i++){
        num = __gcd(num , vec[i]);
    }
    if(num==1){
        cout<<"setwise coprime"<<endl;
        return 0;
    }
    cout<<"not coprime" <<endl;
    return 0;
}

Measured memory_bytes: 50164
{-# LANGUAGE Strict #-}
import           Data.List           ((\\))
import           Data.Vector.Unboxed (Unbox, Vector, (!))
import qualified Data.Vector.Unboxed as V

main :: IO ()
main = do
  n <- readLn
  s <- getLine
  print $ solve n s

solve :: Int -> String -> Int
solve n s = sum [f i k | i <- [0 .. n - 3], k <- [i + 1 .. n - 1]]
  where
    s' = V.fromList s :: Vector Char
    r = scanCount (== 'R') s' :: Vector Int
    g = scanCount (== 'G') s' :: Vector Int
    b = scanCount (== 'B') s' :: Vector Int
    f i k = h $ ['R', 'G', 'B'] \\ [s' ! i, s' ! k]
      where
        h [c] = t c ! k - t c ! i - x
          where
            x = if cond2 then 1 else 0
            cond2 = (k - i) `mod` 2 == 0 && s' ! (i + (k - i) `div` 2) == c
        h _ = 0
    t 'R' = r
    t 'G' = g
    t 'B' = b

scanCount :: Unbox a => (a -> Bool) -> Vector a -> Vector Int
scanCount p = V.scanl' (\c x -> if p x then c + 1 else c) 0


Measured memory_bytes: 5176
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,dp[100010];
vector <int> v[100010];
inline int dfs(int x)
{
	if(dp[x]>=0)return dp[x];
	else{
		if(v[x].empty())return dp[x]=0;
		else{
			for(int i=0;i<v[x].size();++i){
				dp[x]=max(dfs(v[x][i])+1,dp[x]);
			}
		}
	}
	return dp[x];
}
int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
	}
	int ans=0;
	for(int i=1;i<=n;++i)dfs(i);
	for(int i=1;i<=n;++i)ans=max(ans,dp[i]);
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  int N,K;cin>>N>>K;
  vector <int> v(N);
  for(int a;a<N;++a) cin >> v[a];
  sort(v.begin(),v.end(),[](int x, int y)->bool {
    return x>y;
  });
  int ans=0;
  for (int i;i<K;++i){ans +=v[i];}
  cout << ans << endl;
  return 0;
}


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

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

    string S;
    int Q, Ti, Fi;
    char Ci;
    cin >> S >> Q;

    int start = 0, stop = S.length();
    while (Q--) {
        cin >> Ti;
        if (Ti == 1) {
            swap(start, stop);
        } else {
            cin >> Fi >> Ci;
            S.insert(Fi == 1 ? start : stop, 1, Ci);
            if (start < stop)
                stop++;
            else
                start++;
        }
    }
    if (start > stop)
        reverse(S.begin(), S.end());
    cout << S << '\n';

    return 0;
}

Measured memory_bytes: 1040
#include <iostream>

int main() {
    int N, M;
    std::cin >> N >> M;

    int food[M] = {};

    for (int i = 0; i < N; i++) {
        int K;
        std::cin >> K;
        for (int j = 0; j < K; j++) {
            int val;
            std::cin >> val;
            food[val - 1]++;
        }
    }

    int cnt = 0;
    for (int i = 0; i < M; i++) {
        if (food[i] == N) cnt++;
    }

    std::cout << cnt << std::endl;
}


Measured memory_bytes: 256
t1,t2=map(int,input().split())
a1,a2=map(int,input().split())
b1,b2=map(int,input().split())

p=(a1-b1)*t1
q=(a2-b2)*t2
if p>0:
  p*=-1
  q*=-1

if p+q<0:
  print(0)
elif p+q==0:
  print('infinity')
else:
  s,t=divmod(-p,p+q)
  if t!=0:
    print(s*2+1)
  else:
    print(s*2)

Measured memory_bytes: 3064
use std::io::{stdin, stdout, BufReader, BufRead, StdinLock, Write, BufWriter};

fn main() {
    let MOD = 1000000007;
    let (std_in, std_out) = (stdin(), stdout());
    let mut br = BufReader::new(std_in.lock());
    let mut bw = BufWriter::new(std_out.lock());
    
    let s = rs(&mut br);
    let n = s.len();

    let mut p = Vec::new();
    p.push(1);
    for i in 1..n {
        let x = p[i-1];
        p.push((10 * x) % 13);
    }
    p.reverse();

    let mut dp = [[0; 13]; 100005];
    dp[0][0] = 1;
    for i in 0..n {
        if (s[i] == '?') {
            for k in 0..10 {
                let x = (k * p[i]) % 13;
                for m in 0..13 {
                    dp[i+1][(m+x)%13] += dp[i][m];
                    dp[i+1][(m+x)%13] %= MOD;
                }
            }
        } else {
            let x = ((s[i] as usize - 48) * p[i]) % 13;
            for m in 0..13 {
                dp[i+1][(m+x)%13] += dp[i][m];
                dp[i+1][(m+x)%13] %= MOD;
            }
        }
    }
    writeln!(&mut bw, "{}", dp[n][5]);
}


//////////////////////////////////////////////////////////////////////////////////
#[allow(dead_code)]
fn rs(br: &mut BufReader<StdinLock>) -> Vec<char> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().chars().collect()
}

#[allow(dead_code)]
fn rn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> T {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn rvs(br: &mut BufReader<StdinLock>) -> Vec<Vec<char>> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.chars().collect()).collect()
}

#[allow(dead_code)]
fn rvn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> Vec<T> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 9468
#include<bits/stdc++.h>
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<ll> A(N);
    for(int i=0; i<N; i++){
        cin >> A[i];
    }
    ll ans = -1;
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            ll temp = A[i] * A[j];
            string S = to_string(temp);
            bool ok = true;
            for(int k=0; k<S.size()-1; k++){
                if((S[k+1]-'0')-(S[k]-'0') != 1) ok = false;
            }
            if(ok){
                chmax(ans,temp);
            }
        }
    }
    cout << ans << enld;
    return 0;
}


Measured memory_bytes: 3320
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val inputs = IntArray(n) { readLine()!!.toInt() }

    val sorted = inputs.sorted()

    var min = Int.MAX_VALUE
    for (i in 0 until n - (k - 1)) {
        val tmp = sorted[i + k - 1] - sorted[i]
        if (tmp < min) {
            min = tmp
        }
    }

    println(min)
}

Measured memory_bytes: 42068
#include<stdio.h>
int main(){
int a,b;
scanf ("%d %d",&a,&b);
if (a == b) {
printf ("a == b\n");
}
else
if (a > b){
printf ("a > b\n");
}
else
if (a < b){
printf ("a < b\n");
}
return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,A,B,C,D;
cin>>N>>A>>B>>C>>D;
string S; cin>>S;
int a1=0;
int a2=0;
if(D>C){
for(int i=A-1;i<D-3;i++){
if(S.at(i)==S.at(i+1)&&S.at(i)=='#'){
a1++;
break;}}}
else{
for(int i=A-1;i<C-3;i++){
if(S.at(i)==S.at(i+1)&&S.at(i)=='#'){
a1++;
break;}}}
if(a1==1){
cout<<"No"<<endl;}
else{
if(D>C){
cout<<"Yes"<<endl;}
else{
for(int i=B-2;i<=D-2;i++){
if(S.at(i)==S.at(i+1)&&S.at(i+1)==S.at(i+2)&&S.at(i)=='.'){
a2++;
break;}}
if(a2==1){
cout<<"Yes"<<endl;}
else{
cout<<"No"<<endl;}}}}


Measured memory_bytes: 640
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int W, H, N, x, y, a;
    cin >> W >> H >> N;
    int xmin = 0, xmax = W, ymin = 0, ymax = H;
    REP(i, N) {
        cin >> x >> y >> a;
        if (a == 1) {
            amax(xmin, x);
        } else if (a == 2) {
            amin(xmax, x);
        } else if (a == 3) {
            amax(ymin, y);
        } else {
            amin(ymax, y);
        }
    }
    if (xmax > xmin && ymax > ymin) {
        cout << (xmax - xmin) * (ymax - ymin) << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int w[n], total=0;
  rep(i,n){
    cin >> w[i];
    total += w[i];
  }
  int ans  =total,tmp=0;
  rep(i,n-1){
    tmp += w[i];
    if(total-2*tmp<0){
      ans = min(2*tmp-total,ans);
    } else{
      ans = min(-2*tmp+total,ans);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
   int h, n;
   cin>>h>>n;
   vector<int> a(n), b(n);
   rep(i, n) cin>>a[i]>>b[i];

   vector<int> dp(10001, INT_MAX);//nokori j hp de tukatta mp
   dp[h]=0;
   rep(i, n){
      for(int j=10000; j>=0; j--) if(dp[j]!=INT_MAX){
         int dj=max(0, j-a[i]);
         dp[dj]=min(dp[dj], dp[j]+b[i]);
      }
   }

   cout<<dp[0]<<endl;
   return 0;
}


Measured memory_bytes: 3668
n = int(input())
xy = []
for _ in range(n):
    x, y = map(int, input().split())
    xy.append([x, y])

ans = 0
for i in range(n):
    for j in range(n):
        ans += ((xy[i][0]-xy[j][0])**2 + (xy[i][1]-xy[j][1])**2) ** 0.5

print(ans/n)

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

using namespace std;

const long long MOD = 1000000007;

// べき乗の余り計算
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) {
        res += m;
    }
    
    return res;
}


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

    long long answer;

    answer = mod(modpow(10, N, MOD) - modpow(9, N, MOD) * 2, MOD);
    answer = mod(answer + modpow(8, N, MOD), MOD);

    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 3560
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 998244353;
const int MAXN = 200010, LOG=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
ll dp[MAXN*2], tav[MAXN];
int X[MAXN];
int col[MAXN], comp[MAXN], C[MAXN];
vector<pii> G[MAXN];

bool dfs(int node, int c, int cid){
	col[node]=c;
	comp[node]=cid;
	for (pii p:G[node]){
		if (comp[p.first] && col[p.first]!=c^p.second) return 0;
		if (!comp[p.first] && !dfs(p.first, p.second^c, cid)) return 0;
	}
	return 1;
}

ll solve(ll k){
	//debug(k)
	for (int i=1; i<=n; i++) G[i].clear();
	if (k<n){
		for (int i=1; i+k<=n; i++){
			G[i].pb({i+k, 0});
			G[i+k].pb({i, 0});
		}
		for (int i=1; i<=k; i++){
			G[i].pb({i+n-k, 1});
			G[i+n-k].pb({i, 1});
		}
	}
	else{
		k-=n;
		for (int i=1; i+k<=n; i++){
			G[i].pb({i+k, 1});
			G[i+k].pb({i, 1});
		}
		for (int i=1; i<=k; i++){
			G[i].pb({i+n-k, 0});
			G[i+n-k].pb({i, 0});
		}
	}
	memset(comp, 0, sizeof(comp));
	//memset(col, 0, sizeof(col));
	int cnt=0;
	for (int i=1; i<=n; i++) if (!comp[i]){
		if (!dfs(i, 0, i)) return 0;
		cnt++;
	}
	
	for (int i=1; i<=n; i++) C[comp[i]]=-1;
	ll res=0;
	for (int i=1; i<=n; i++){
		if (X[i] && (C[comp[i]]==-1 || C[comp[i]]==col[i])){
			res+=tav[cnt-(C[comp[i]]==-1)];
		}
		if (C[comp[i]]==-1) C[comp[i]]=X[i]^col[i], cnt--;
		else if (C[comp[i]]!=col[i]^X[i]) return res;
	}
	res++;
	return res%mod;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	tav[0]=1;
	for (int i=1; i<MAXN; i++) tav[i]=tav[i-1]*2%mod;
	cin>>n;
	char ch;
	for (int i=1; i<=n; i++) cin>>ch, X[i]=ch-'0';
	
	for (int i=1; i<2*n; i++) if (2*n%i==0) dp[i]=solve(i);
	dp[2*n]=solve(0);
	//debug("done")
	
	for (int i=1; i<=2*n; i++) for (int j=2*i; j<=2*n; j+=i) if (2*n%j==0) dp[j]=(dp[j]-dp[i])%mod;
	for (int i=1; i<=2*n; i++) ans=(ans+dp[i]*i)%mod;
	//for (int i=1; i<=2*n; i++) debug2(i, dp[i])
	if (ans<0) ans+=mod;
	cout<<ans<<'\n';
	
	return 0;
}


Measured memory_bytes: 28160
#include<stdio.h>
long long int A[100][100],B[100][100],C[100][100];
main()
{
	int n,m,l,k;
	
	int c1,c2;
	
	scanf("%d %d %d",&n,&m,&l);
	
	for(c1=0;c1<n;c1++){
		for(c2=0;c2<m;c2++){
			scanf("%d",&A[c1][c2]);
		}
	}
	
	for(c1=0;c1<m;c1++){
		for(c2=0;c2<l;c2++){
			scanf("%d",&B[c1][c2]);
		}
	}
	
	
	for(c1=0;c1<n;c1++){
		for(c2=0;c2<l;c2++){
			for(k=0;k<m;k++){
				C[c1][c2]+=A[c1][k]*B[k][c2];
			}
		}
	}
	
	for(c1=0;c1<n;c1++){
		for(c2=0;c2<l;c2++){
			printf("%lld",C[c1][c2]);
			if(c2!=l-1)printf(" ");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 836
day = input()
if day == 'SUN':
  day = 0
elif day == 'MON':
  day = 1
elif day == 'TUE':
  day = 2
elif day == 'WED':
  day = 3
elif day == 'THU':
  day = 4
elif day == 'FRI':
  day = 5
elif day == 'SAT':
  day = 6
print(7 - day)

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

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

int main() {

  int N;
  cin >> N;
  
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  
  int L[N+1];
  int R[N+1];
  
  L[0]=0;
  for (int i = 0; i < N; i++) {
    L[i+1]=gcd(L[i],A[i]);
  }
  R[N]=0;
  for (int i = N-1; i >= 0; i--) {
    R[i]=gcd(A[i],R[i+1]);
  }
  
  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans = max(ans, gcd(L[i], R[i+1]));
  }
  
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
std::vector<bool> IsPrime;
int q;

void sieve(size_t max){
    if(max+1 > IsPrime.size()){     // resizeで要素数が減らないように
        IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保
    } 
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;      // 素数ではない
}

int main(){
sieve(100003);
cin>>q;
int count[100005]={0};
for(int i =3;i<100003;i++){
count[i]=count[i-1];
if(IsPrime[i]&&IsPrime[(i+1)/2]){
count[i]++;
}
}
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
cout<<count[r]-count[l-1]<<endl;
}
return 0;

}

Measured memory_bytes: 1024
from sys import stdin
from collections import deque

K = int(stdin.readline())

deque = deque()
for i in range(1, 10):
    deque.append(i)

for i in range(K - 1):
    s = deque.popleft()
    for j in range(-1, 2):
        add = (s % 10) + j
        if 0 <= add <= 9:
            deque.append(s * 10 + add)

print(deque.popleft())


Measured memory_bytes: 12404
n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[0]*n
l1[0]+=1
c=0 #ループに入る前までの移動回数
now=0#現在位置
ne=a[now]-1 #次の移動位置
while True:
    if c==k:
        print(now+1)
        exit()
    if l1[ne]==0:
        l1[ne]+=1
        now=ne
        ne=a[now]-1
        c+=1
    else:
        now=ne
        ne=a[now]-1
        c+=1
        break

roop_c=0
while True:
    if c+roop_c==k:
        print(now+1)
        exit()
    if l1[ne]==1:
        l1[ne]+=1
        now=ne
        ne=a[now]-1
        roop_c+=1
    else:break

re=(k-c)%roop_c
if re==0:print(now+1)
else:
    for i in range(re):
        if i==re-1:print(ne+1)
        ne+=-ne+a[ne]-1

Measured memory_bytes: 32308
#include <bits/stdc++.h>
using namespace std;
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mii map<ll,ll>
#define pii pair<ll,ll>
#define vi vector<ll>
#define endl "\n"
#define deb(x) cout << #x << "=" << x << endl
const ll mod = 1e9+7;

ll msum(ll a,ll b,ll m) { return (a%m+b%m)%m; }
ll msub(ll a,ll b,ll m) { return (a%m-b%m)%m; }
ll mpro(ll a,ll b,ll m) { return ((a%m)*(b%m))%m; }
ll m_m(ll a,ll b,ll m);
ll fxp(ll a,ll b,ll m);
void swap(ll &a,ll &b){ ll t=a; a=b; b=t;}

struct act
{
    int a,b,c;
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        ll n,i;
        cin>>n;
        vector<act> v;
        fo(i,n)
        {
            act tp;
            cin>>tp.a>>tp.b>>tp.c;
            v.pb(tp);
        }
        ll dp[n][3];
        dp[0][0]=v[0].a;
        dp[0][1]=v[0].b;
        dp[0][2]=v[0].c;
        for(i=1;i<n;i++)
        {
            dp[i][0]=v[i].a+max(dp[i-1][1],dp[i-1][2]);
            dp[i][1]=v[i].b+max(dp[i-1][0],dp[i-1][2]);
            dp[i][2]=v[i].c+max(dp[i-1][0],dp[i-1][1]);
        }
        ll ans=max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
        cout<<ans<<endl;
    }
 return 0;
}
ll fxp(ll a,ll b,ll m) {
    if(b==0)
        return 1;
    if(b%2==0)
        return fxp(m_m(a,a,m),b/2,m);
    return m_m(fxp(a,b-1,m),a,m);
}
ll m_m(ll a,ll b,ll m) 
{
    ll res=0;
    a=a%m;
    while(b)
    {
        if(b&1)
        {
            res+=a; 
            res=res%m;
        }
        a=(a*2)%m;
        b=b/2;
    }
    return res;
}

Measured memory_bytes: 6912
#include<iostream>
#define INF 9223372036854775807
using namespace std;

long long cardnumber[2 * 100005];

int main() {
    int N;
    long long min_sub = INF;
    long long all_sum = 0, snuke_sum = 0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> cardnumber[i];
        all_sum += cardnumber[i];
    }
    for (int i = 0; i < N - 1; i++) {
        snuke_sum += cardnumber[i];
        min_sub = min(min_sub, abs(2 * snuke_sum - all_sum));
    }
    cout << min_sub << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<58;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Graph{
	private:
	int V;
	vvp g;
	public:
	vl DIJ(int s){
		priority_queue<pll> que;
		vl d(V,INF);
		d[s]=0;
		que.push({0,s});
		while(!que.empty()){
			pll p=que.top();
			que.pop();
			int v=p.second;
			if(d[v]<-p.first) continue;
			for(int i=0;i<g[v].size();i++){
				ll F=g[v][i].first,S=g[v][i].second;
				if(d[F]>d[v]+S){
					d[F]=d[v]+S;
					que.push({-d[F],F});
				}
			}
		}
		return d;
	}
	Graph(int v){
		V=v;
		g=vvp(v);
	}
	void add_edge(int s,int t,int c){
		g[s].push_back({t,c});
		g[t].push_back({s,c});
	}
};

int n,q,k;

int main(){
	cin>>n;
	Graph g(n);
	for(int i=1;i<n;i++){
		int u,v,c;
		cin>>u>>v>>c;
		g.add_edge(u-1,v-1,c);
	}
	cin>>q>>k;
	vl d=g.DIJ(k-1);
	for(int i=0;i<q;i++){
		int u,v;
		cin>>u>>v;
		cout<<d[u-1]+d[v-1]<<endl;
	}
}

Measured memory_bytes: 9460