akhauriyash/Code-Regression huggingface dataset:
use std::io::stdin;
use std::iter::Iterator;
use std::collections::VecDeque;
use std::collections::HashMap;

fn solve(cin: &mut ConsoleInputWrapper) {
    let n = cin.input().parse().unwrap();

    let mut a: Vec<usize> = Vec::new();
    let mut b: Vec<usize> = Vec::new();
    let mut c: Vec<usize> = Vec::new();

    for i in 0..n {
        a.push(cin.input().parse().unwrap());
    }
    for i in 0..n {
        b.push(cin.input().parse().unwrap());
    }
    for i in 0..n - 1 {
        c.push(cin.input().parse().unwrap());
    }

    let mut score = 0;
    for i in 0..n {
        score += b[a[i] - 1];
        if i + 1 < n && a[i] + 1 == a[i + 1] {
            score += c[a[i] - 1];
        }
    }
    println!("{}",score);
    ()
}

//Other Functions Here

fn main() {
    let mut cin = ConsoleInputWrapper::new();
    solve(&mut cin);
}

fn factorization(value: i64) -> HashMap<i64, usize> {
    let sqrt = f64::sqrt(value.clone() as f64);
    let mut value = value;
    let mut map = HashMap::new();
    let mut p = 2;
    while p.clone() as f64 <= sqrt {
        let mut count = 0;
        while (value % p.clone()) == 0 {
            count += 1;
            value /= p.clone();
        }
        if count > 0 {
            map.insert(p.clone(), count);
        }
        p += 1;
    }
    if value != 1 {
        map.insert(value, 1);
    }
    map
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b.clone(), a % b)
    }
}

fn min(a: i32, b: i32) -> i32 {
    if a < b { a } else { b }
}

fn max(a: i32, b: i32) -> i32 {
    if a > b { a } else { b }
}

struct ConsoleInputWrapper {
    queue: VecDeque<String>
}

impl ConsoleInputWrapper {
    fn new() -> ConsoleInputWrapper {
        ConsoleInputWrapper {
            queue: VecDeque::new()
        }
    }
    fn input(&mut self) -> String {
        if self.queue.len() <= 0 {
            let mut s = String::new();
            stdin().read_line(&mut s).unwrap();
            let list: Vec<&str> = s.split_whitespace().collect();
            for string in list {
                self.queue.push_back(String::from(string));
            }
        }
        self.queue.pop_front().unwrap()
    }
}

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

int main() {
    int a,b;
    cin >> a >> b;
    if(a % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }else if(b % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }else if( (a + b) % 3 == 0){
        cout << "Possible" << endl;
        return 0;
    }

    cout << "Impossible" << endl;
}

Measured memory_bytes: 256
from collections import defaultdict
import heapq


n, m = map(int, input().split())
jobs = defaultdict(list)

for i in range(n):
    a, b = map(int, input().split())
    jobs[a].append(-b)


ans = 0
jobs_h = list()
for i in range(1, m + 1):
    for job in jobs[i]:
        heapq.heappush(jobs_h, job)

    if len(jobs_h) != 0:
        # b -> -b -> b
        value = heapq.heappop(jobs_h)
        ans -= value

print(ans)

Measured memory_bytes: 27716
import sys

def main():
    input = sys.stdin.readline
    N, K, Q = map(int, input().split())
    P = [0] * N
    for _ in range(Q):
        a = int(input())
        P[a-1] += 1

    for p in P:
        if p > Q - K:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 4680
<?php
error_reporting(0);
//$N = explode(" ",trim(fgets(STDIN)));
//list($D,$X) = explode(" ",trim(fgets(STDIN)));
$N=trim(fgets(STDIN));
$A = explode(" ",trim(fgets(STDIN)));
$p = 0;
$tot=0;
$diff = array();
foreach($A as $a) {
  $tot += abs($a - $p);
  $diff[] = abs($a - $p);
  $p = $a;
}
$tot += abs($p);
$diff[]=abs($p);
for($i=0;$i<$N;$i++) {
  $base = 0;
  if (isset($A[$i-1])) {
    $base = $A[$i-1];
  }
  //トータル距離+増える距離-減る距離...なんかおかしいような・・・
  printf("%d\n",$tot+abs($A[$i+1]-$base)-($diff[$i]+$diff[$i+1]));
}


Measured memory_bytes: 36452
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF (1e9 + 5)
#define MOD (int)(1e9 + 7) 

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a;
    cin >> a;
    int ans = 0;
    int temp = 0;
    for(int i = 0; i < a.size(); ++i) {
        if(a[i] == 'R') {
            temp++;
        }
        else {
            temp = 0;
        }
        ans = max(ans, temp);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <vector>

using namespace std;

//index??\??????????´?????????£???m???????????????
bool Solve(int index, int m, const vector<int>& A)
{
    if(index >= A.size()) return false;
    if(m == 0) return true;

    return Solve(index + 1, m, A) || Solve(index + 1, m - A[index], A);
}


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

    vector<int> A(n + 1);
    for(int i = 0, input; i < n && cin >> input; ++i)
        A[i] = input;

    int q;
    cin >> q;
    for(int i = 0; i < q; ++i)
    {
        int m;
        cin >> m;

        cout << (Solve(0, m, A) ? "yes" : "no") << endl;
    }


    return 0;
}

Measured memory_bytes: 3096
n, m = map(int, input().split())

cnt = 1

for i in range(1, int(m ** 0.5) + 1):
    if m % i == 0:
        b = m // i
        if i * n <= m:
            cnt = max(cnt, i)
        if b * n <= m:
            cnt = max(cnt, b)
print(cnt)


Measured memory_bytes: 3060
/**
 *   Author: Praveen Ojha
 *   Created: 23 March 2019
 *   Time: 18:49:47
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long double ld;
typedef pair<int,int> pii;

int32_t main(){__
	int N,W;
	cin>>N>>W;
	vector <int> dp(W+1); // dp[i] maximum value obtainable till weight exactly i

	for(int i=0;i<N;i++){
		int weight,val;
		cin>>weight>>val;
		for(int weight_already=W-weight;weight_already>=0;weight_already--){
			dp[weight_already+weight]=max(dp[weight_already+weight],dp[weight_already]+val);
		}
		// for(int j=0;j<=W;j++)
		// 	cout<<dp[j]<<" ";
		// cout<<"\n";
	}
	cout<<dp[W]<<"\n";
return 0;
}

Measured memory_bytes: 1024
N, M, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0] * (N + 1)
sb = [0] * (M + 1)
for i in range(N):
	sa[i+ 1] = sa[i] + a[i]
for i in range(M):
	sb[i + 1] = sb[i] + b[i]
r = M
books = 0
for i in range(N+1):
	if sa[i] > k: break
	while sa[i] + sb[r] > k:
		r -= 1
	books = max(books, i+r)
print(books)

Measured memory_bytes: 47440
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    int N,i = 1;
    cin >> N;
    for(;i <= N;i <<= 1){
        if(i*2 > N){
            cout << i << endl;
        }
    }
}

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

int main() {
  int Sum=0, min=10;
  vector<int> a(5);
  rep(i, 5){
    cin >> a.at(i);
    if(a.at(i)%10==0) Sum=Sum+a.at(i);
    else {
      if(min>a.at(i)%10) min=a.at(i)%10;
      Sum=Sum+a.at(i)-a.at(i)%10+10;
    }
  }
  cout << Sum-10+min << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define IOS ios::sync_with_stdio(0);cin.tie(0);
using namespace std;

int main(){
	IOS;
	int N,sum=0,c=0,m=10005;
	vector<int> t,f;
	cin>>N;
	for(int i=0;i<N;i++){
		int a;
		cin>>a;
		sum=sum+a;
		if(a%10==0){
			t.push_back(a);
		}
		else {
			f.push_back(a);
			c++;
		}
	}
	if(f.size()==0){
		cout<<0<<endl;
	}
	else if(sum%10==0){
		for(int i=0;i<c;i++){
			m=min(m,f[i]);
		}
		cout<<sum-m<<endl;
	}	
	
		else
			cout<<sum<<endl;
		
	
	
	
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007



int main(){
  
  int n;
  cin >> n;
  vector<ll> v(n);
  rep(i,n)cin >> v[i];
  vector<ll> s(n+1,0);
  rep(i,n)s[i+1] = s[i]+v[i];
  ll res = 0,res_ = 0;
  ll ch = 0,ch_ = 0;
  bool pre = 0,pre_ = 1;
  rep(i,n){
    if(pre){
      if(s[i+1]+ch >= 0){
        res += s[i+1]+ch+1;
        ch -= s[i+1]+ch+1;
      }
      pre = false;
    }else{
      if(s[i+1]+ch <= 0){
        res += abs(s[i+1]+ch)+1;
        ch += abs(s[i+1]+ch)+1;
      }
      pre = true;
    }
    if(pre_){
      if(s[i+1]+ch_ >= 0){
        res_ += s[i+1]+ch_+1;
        ch_ -= s[i+1]+ch_+1;
      }
      pre_ = false;
    }else{
      if(s[i+1]+ch_ <= 0){
        res_ += abs(s[i+1]+ch_)+1;
        ch_ += abs(s[i+1]+ch_)+1;
      }
      pre_ = true;
    }
  }
  cout << min(res,res_) << endl;
  
  






  return 0;
}

Measured memory_bytes: 1792
import scala.io.StdIn.{readInt, readLine};

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val arr = readLine.split(" ").map(_.toLong);
        val cnt = mergeSort(arr, n);
        println(arr.mkString(" "));
        println(cnt);
        
    }
    def mergeSort(arr: Array[Long], n: Int): Int = {
        def _mergeSort(first: Int, last: Int): Int = {
            if (last - first > 0) {
                val pivot = (first + last) / 2;
                val cnt1 = _mergeSort(first, pivot);
                val cnt2 = _mergeSort(pivot + 1, last);
                val cnt3 = merge(arr, first, last, pivot);
                cnt1 + cnt2 + cnt3;
            } else {
                0;
            }
        }
        _mergeSort(0, n - 1);
    }
    
    def merge(arr: Array[Long], first: Int, last: Int, pivot: Int): Int = {
        val tmpArr = (first to pivot).map(arr(_)).toArray;
        var ptr1 = 0;
        var ptr2 = pivot + 1;
        var cnt = 0
        for (i <- (first to last)) {
            cnt += 1;
            if (ptr1 >= tmpArr.length) {
                arr(i) = arr(ptr2);
                ptr2 += 1;
            } else if (ptr2 > last) {
                arr(i) = tmpArr(ptr1);
                ptr1 += 1;
            } else {
                if (arr(ptr2) < tmpArr(ptr1)) {
                    arr(i) = arr(ptr2);
                    ptr2 += 1;
                } else {
                    arr(i) = tmpArr(ptr1);
                    ptr1 += 1;
                }
            }
        }
        cnt;
    }
}


Measured memory_bytes: 452884
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = a; i < 1000000000; i += a) {
		if (i%b == c) { cout << "YES" << endl; return 0; }
	}
	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
s = {}
for i in a:
  if i not in s:
    s[i] = 1
  else:
    s[i] += 1
ans = sum(a)
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  if b not in s:
    print(ans)
    continue
  ans += (c - b) * s[b]
  print(ans)
  if c not in s:
    s[c] = 0
  s[c] += s[b]
  s[b] = 0


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<pair<int, int>> z[n];
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    for(int j = 0; j < a; j++){
      int x, y;
      cin >> x >> y;
      z[i].push_back(make_pair(x, y));
    }
  }
  
  // 正直者を1としてビットで管理
  int ans = 0;
  for(int i = 0; i < pow(2, n); i++){
    bool flag = true;
    for(int j = 0; j < n; j++){
      if((i >> j) & 1){
        for(int k = 0; k < z[j].size(); k++){
          if(z[j].at(k).second == 1 && (i & (1 << (z[j].at(k).first - 1))) == 0) flag = false;
          if(z[j].at(k).second == 0 && ((i >> (z[j].at(k).first - 1)) & 1) == 1) flag = false;
        }
      }
    }
    
    if(flag){
      int count = 0;
      for(int j = 0; j < n; j++){
        if((i >> j) & 1) count++;
      }
      ans = max(ans, count);
    }
  }
  
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
#define INF 1000000001;

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

  vector<long long> a(n);
  vector<long long> b(n);
  vector<long long> c(n);

  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; i++) {
    cin >> c[i];
  }

  long long ans = 0;

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  
  for (int i = 0; i < n; i++) {
    long long ab = (lower_bound(a.begin(), a.end(), b[i]) - a.begin());
    long long bc = n - (upper_bound(c.begin(), c.end(), b[i]) - c.begin()); 
    ans += ab*bc;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define el cout << "\n"
#define pb push_back
#define f first
#define s second
#define arrondi(a) (long long)floor(a+0.5);
#define NIL -1
ll N=500005;
ll MAX=9223372036854775807;
ll MOD=1000000007;
long double PI =4*atan(1);
ll n , m ,k;
ll nbr;

int main()
{
	IOS;


        ll n;
        cin >> n;
    vector<ll> L;
    for(int i=0;i<n;i++)
    {
        ll x;
        cin >> x;
        L.push_back(x);
    }

    vector<vector<ll>> dp(n+1, vector<ll>(n+1,0));
    if(n%2==0)
    {
        for(int i=0;i<n;i++)
            dp[i][i]=-L[i];
        for(int len=2;len<=n;len++)
    {
        for(int i=0;i<=n-len;i++)
        {
            ll j=i+len-1;
            if(len%2==0)
                dp[i][j]=max(dp[i+1][j]+L[i],dp[i][j-1]+L[j]);
            else
                dp[i][j]=min(dp[i+1][j]-L[i],dp[i][j-1]-L[j]);

        }
    }
    }
    else
    {
       for(int i=0;i<n;i++)
            dp[i][i]=L[i];
        for(int len=2;len<=n;len++)
    {
        for(int i=0;i<=n-len;i++)
        {
            ll j=i+len-1;
            if(len%2==1)
                dp[i][j]=max(dp[i+1][j]+L[i],dp[i][j-1]+L[j]);
            else
                dp[i][j]=min(dp[i+1][j]-L[i],dp[i][j-1]-L[j]);

        }
    }
    }
    cout << dp[0][n-1];


    return 0;
}


Measured memory_bytes: 70784
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s << "[";
    for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
    s << "]";
    return s;
}

#define ALL(a) (a).begin(), (a).end()

static int ans = 0;
static int N;
static vector<int> a;
static vector<int> diff;

void dfs(int idx) {
    if (idx == N) {
        // check
        for (int i = 0; i < N; i++) {
            if ((a[i] + diff[i]) % 2 == 0) {
                ans++;
                break;
            }
        }
        return;
    }
    for (int d = -1; d <= 1; d++) {
        diff[idx] = d;
        dfs(idx + 1);
    }
}

int main() {
    cin >> N;

    a.resize(N);
    diff.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    dfs(0);

    cout << ans << endl;

    return 0;
}


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

using namespace std;


int main() {

    int N;
    cin >> N;
    vector <string> s(N);
    for (int l = 0; l < N; ++l) {
        cin >> s[l];
    }
    int ans = 0;
    // ABの数
    int count = 0;
    // Aでおわる
    int isA = 0;
    // Bでおわる
    int isB = 0;
    int isAB = 0;
    for (int i = 0; i < N; ++i) {
        string temp = s[i];
        int M = temp.length();
        bool can = false;
        for (int j = 0; j < M; ++j) {
            char ch = temp[j];
            if (j == 0) {
                if (ch == 'B') {
                    isB++;
                    can = true;
                }
            }
            if (j == M - 1) {
                if (ch == 'A') {
                    isA++;
                    if (can) {
                        isAB++;
                        isA--;
                        isB--;
                    }
                }
            }
            if (j < M - 1) {

                if (ch == 'A' && temp[j + 1] == 'B') { count++; }
            }
        }
    }
    // cout << count << isA << isB << isAB << endl;

    int ab = min(isA, isB);

    if (N == 1) {
        ans = count;
    }
    // isA == isB && isAB == 0
    if (N  > 1) {

        if (isA == isB && isAB == 0) {
            ans = ab + count; //ok
        }
        if (isA + isB  == 0 && isAB > 0) {
            ans = ab + count + isAB -1; // ok
        }
        if (isA != isB && isAB == 0){
            /**
             * 2
             * BABA
             * BA
             *
             */
            ans = count + ab;//ok
        }
        if (isA + isB  > 0 && isAB > 0) {
            /**
             * 2
             * BABA
             * BAB
             * isA =1
             * isB =2
             * is AB = 1
             */

            /**
             * 3
             * BABA
             * BABA
             * BAB
             *
             * isA =1
             * isB =2
             * is AB = 1
             */
            ans = count + ab + isAB;


        }
    }



//
//            if (isAB > 0){
//                ans = ab + count - 1;
//            }else {
//                ans = ab + count - isAB;
//            }
//        } else {
//            ans = ab + count;
//
//        }
//    }




    // isAB  > 1



//    if (N  > 1) {
//        if (isA == isB) {
//            if (isAB > 0){
//                ans = ab + count - 1;
//            }else {
//                ans = ab + count - isAB;
//            }
//        } else {
//            ans = ab + count;
//
//        }
//    }
    // ans = ab + count;
    cout << ans << endl;
}

Measured memory_bytes: 768
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, t[100008], a[100008], fix[100008];
ll MOD = 1e9+7;
string str;

int main(){
	cin >> n;
	for(ll i = 1; i <= n; i++){cin >> t[i];}
	for(ll i = 1; i <= n; i++){cin >> a[i];}
	
	ll buf = 0;
	ll ans = 1;
	memset(fix, 0, sizeof(fix));
	for(ll i = 1; i <= n; i++){
		if(t[i] > buf){
			if(t[i] <= a[i]){
				fix[i] = t[i];
				buf = t[i];
			}
			else{
				ans = 0;
			}
		}
	}
	
	buf = 0;
	for(ll i = n; i >= 1; i--){
		if(a[i] > buf){
			if(a[i] <= t[i] && (fix[i] == 0 || fix[i] == a[i])){
				fix[i] = a[i];
				buf = a[i];
			}
			else{
				ans = 0;
			}
		}
	}
	
	for(ll i = 1; i <= n; i++){
		if(fix[i] == 0){
			ans *= min(t[i], a[i]);
			ans %= MOD;
		}
	}
	
	cout << ans << endl;
	return 0;
}

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

namespace ConsoleApp15
{
    class Class392
    {
        static void Main()
        {
            var ABK = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long A = ABK[0], B = ABK[1], K = ABK[2];
            if (A > K)
            {
                Console.WriteLine($"{A-K} {B}");
            }
            else if (A + B > K)
            {
                Console.WriteLine($"{0} {A+B-K}");
            }
            else
            {
                Console.WriteLine($"{0} {0}");
            }
        }
    }
}


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

int main() {
	string s, t = "CODEFESTIVAL2016";
  	cin >> s;
  
  	int cnt = 0;
  	for (int i = 0; i < s.size(); i++) {
    	if (s[i] != t[i]) cnt++;
    }
  
  	cout << cnt << endl;
  	return 0;
}

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

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

  int ans = 0,a = 0,b = 0,both = 0;
  for(int i = 0;i < N;i++) {
    string S;
    cin >> S;
    for(int j = 0;j < S.size()-1;j++) {
      if(S.at(j) == 'A' && S.at(j+1) == 'B') ans++;
    }
    if(S.at(0) == 'B' && S.at(S.size()-1) == 'A') {
      both++;
      continue;
    }
    if(S.at(0) == 'B') b++;
    if(S.at(S.size()-1) == 'A') a++;
   
  }

  if(both != 0 && a == 0 && b == 0) ans += both-1;
  else ans += both + min(a,b);
  cout << ans << endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

/* grid 4-coloring, Chebyshev Distance */
/*
 * 曼哈顿距离是一个立着的正方形, 不方便处理.    d = |xi-xj|+|yi-yj|
 * 将矩阵旋转45°, 转为切比雪夫距离(正方形).     d = max{|xi-xj|,|yi-yj|}
 */

const int maxn = 510;
const char color[2][2] = { {'R','G'},{'B','Y'} };
char ans[maxn][maxn];
int H,W,d;

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    while (cin >> H >> W >> d) {
        int c1,c2; c1 = c2 = 0;
        for (int i = -maxn*2; i <= maxn*2; i += d) {
            for (int j = -maxn*2; j <= maxn*2; j += d) {
                FOR(x,0,d) FOR(y,0,d) {
                    const int c = color[c1][c2];
                    const int I = i+x;
                    const int J = j+y;
                    const int ii = (I+J)/2;
                    const int jj = (I-J)/2;
                    if (0 <= ii && ii < H && 0 <= jj && jj < W)
                        ans[ii][jj] = c;
                }
                c2 ^= 1;
            }
            c1 ^= 1;
        }
        FOR(i,0,H) {
            FOR(j,0,W)
                cout << ans[i][j];
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 768
program ms_solution
  implicit none
  integer(8), parameter :: inf = 1e16
  integer :: n, i, j, k, l, u
  integer(8) :: x(15) = 0, y(15) = 0, p(15) = 0
  integer(8) :: mx(0:2 ** 15, 15) = inf, my(0:2 ** 15, 15) = inf
  integer(8) :: m(0:15) = inf
  logical :: used(0:2 ** 15)
  read(*,*) n
  do i = 1, n
    read(*,*) x(i), y(i), p(i)
  end do
  do i = 1, n
    mx(:, i) = min(abs(x(i)), abs(y(i))) * p(i)
    my(:, i) = mx(:, i)
  end do
  u = lshift(1, n) - 1
  do i = 0, u
    do j = 1, n
      if (.not.btest(i, j - 1)) cycle
      do l = 1, n
        mx(i, l) = min(mx(i, l), abs(x(l) - x(j)) * p(l))
        my(i, l) = min(my(i, l), abs(y(l) - y(j)) * p(l))
      end do
    end do
  end do
  call dfs(0, 0, 1)
  do i = 0, n
    write(*,'(i0)') m(i)
  end do
contains
  recursive subroutine dfs(ix, iy, cnt)
    integer, intent(in) :: ix, iy, cnt
    integer :: k, i, j
    if (cnt == n + 1) then
      k = popcnt(ix) + popcnt(iy)
      m(k) = min(m(k), sum(min(mx(ix, 1:n), my(iy, 1:n))))
      return
    end if
    call dfs(ibset(ix, cnt - 1), iy, cnt + 1)
    call dfs(ix, ibset(iy, cnt - 1), cnt + 1)
    call dfs(ix, iy, cnt + 1)
  end
end program ms_solution

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

struct state{
  int y,x,d,t;
  state(int a,int b,int c,int e):y(a),x(b),d(c),t(e){}
};

int vis[55][55][4][4];
const string dir = "^?>?v?<?";
const int dx[] = {0,1,1,1,0,-1,-1,-1}, dy[] = {-1,-1,0,1,1,1,0,-1};

int main(){
  int h,w;
  cin >> h >> w;
  vector<string> s(h);
  rep(i,h)cin >> s[i];

  int y,x,d;
  rep(i,h)rep(j,w){
    rep(k,8){
      if(s[i][j] == dir[k]){
	y = i, x = j, d = k/2;
      }
    }
  }

  queue<state> q;
  rep(i,4){
    int ny = y+dy[(2*d+i)%8], nx = x+dx[(2*d+i)%8];
    if(!in_range(ny,0,h) || !in_range(nx,0,w) || s[ny][nx] == '#'){
      vis[y][x][d][i] = 1;
      q.push(state(y,x,d,i));
    }
  }
  
  while(q.size()){
    state p = q.front(); q.pop();
    int y = p.y, x = p.x, d = p.d, t = p.t;
    //cout << y << " " << x << " " << d << " " << t << endl;
    if(s[y][x] == 'G')break;
    
    //change hand
    rep(i,4){
      if(i%2==0 && abs(t-i)>2)continue;
      if(i%2==1 && abs(t-i)>1)continue;

      int nt = (2*d+i)%8;
      int ty = y+dy[nt], tx = x+dx[nt];
      if(in_range(ty,0,h) && in_range(tx,0,w) && s[ty][tx] != '#')continue;
      if(vis[y][x][d][i])continue;

      vis[y][x][d][i] = 1;
      q.push(state(y,x,d,i));
    }

    //turn right
    if(t>=2 && !vis[y][x][(d+1)%4][t-2]){
      vis[y][x][(d+1)%4][t-2] = 1;
      q.push(state(y,x,(d+1)%4,t-2));
    }

    //turn left
    if(t<2 && !vis[y][x][(d+3)%4][t+2]){
      vis[y][x][(d+3)%4][t+2] = 1;
      q.push(state(y,x,(d+3)%4,t+2));
    }

    //go straight
    if(1<=t && t<=2){
      int ny = y+dy[2*d], nx = x+dx[2*d];
      if(!in_range(ny,0,h) || !in_range(nx,0,w))continue;

      if(s[ny][nx] == '#')continue;
      if(vis[ny][nx][d][t+1])continue;
      vis[ny][nx][d][t+1] = 1;
      q.push(state(ny,nx,d,t+1));
    }
  }

  int ans = 0;
  rep(i,h)rep(j,w){
    int cnt = 0;
    rep(k,4)rep(l,4){
      cnt += vis[i][j][k][l];
    }
    //cout << i << " " << j << " " << cnt << endl;
    if(cnt)ans++;
    if(cnt==0 && s[i][j] == 'G'){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1412
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BCs = [list(map(int,input().split())) for _ in range(Q)]
max_A = max(A)

# Aの値について数列を作る
# A_num = [A.count(i) for i in range(10 ** 5 + 1)]

A_num = [0 for i in range(10 ** 5 + 1)]
for a in A:
    A_num[a] += 1

Si = sum(A)

for BC in BCs:
    # BC[0] ...　置換前の値
    # BC[1] ...　置換後の値
    
    if A_num[BC[0]] > 0: 
        Si += A_num[BC[0]] * (BC[1] -BC[0])
        A_num[BC[1]] += A_num[BC[0]]
        A_num[BC[0]] = 0

    print(Si)

Measured memory_bytes: 32752
#include <bits/stdc++.h>
#define int long long int
#define pb push_back

#define mod 1000000007
#define sp fixed<<setprecision(12)
using namespace std;
/*
const int MAX=10000005;
vector<int> primes;
bitset<MAX> is_prime;
void sieve(){
    is_prime.set();
    is_prime[0]=is_prime[1]=0;
    for(int i=4;i<MAX;i+=2){
        is_prime[i]=0;
    }
    for(int i=3;i*i<MAX;i+=2){
        if(is_prime[i]){
            primes.pb(i);
            for(int j=i*i;j<MAX;j+=i){
                is_prime[j]=0;
            }
        }
    }
}
*/
/*
void lcs(char s1[],char s2[]){
    int n=strlen(s1);
    int m=strlen(s2);
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int sum=0;
            if(s1[i-1]==s2[j-1]){
                sum=1+dp[i-1][j-1];
            }
            else{
                sum=max(dp[i-1][j],dp[i][j-1]);
            }
            dp[i][j]=sum;
        }
    }
    
    int index=dp[n][m];
    //cout<<index<<endl;
    char ans[index+1];
    ans[index]='\0';
    index--;
    int x=n;
    int y=m;
    while(x>0 and y>0){
        if(dp[x-1][y]==dp[x][y-1] and dp[x-1][y]!=dp[x][y]){
            ans[index]=s1[x-1];
            index--;
            x--;
            y--;
        }else if(dp[x-1][y]>dp[x][y-1]){
            x--;
        }else{
            y--;
        }

    }
    //reverse(ans.begin(),ans.end());

    cout<<ans;
    return;
}
*/



int32_t main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    //double    pi=3.14159265358979323846;
    //sieve();
    int t=1;
    
    //cin>>t;
    
    for(int tc=1;tc<=t;tc++){
        int n;
        cin>>n;
        if(n>=30){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    
    return 0;
    
}

Measured memory_bytes: 3636
n,m = map(int,input().split())
A = list(map(int,input().split()))
B = [list(map(int,input().split())) for i in range(m)]

#A=sorted(A,reverse=1)

for i in range(n):
    B.append([1,A[i]])
B=sorted(B,reverse=1,key=lambda x: x[1])

#print(A)
#print(B)



ans = 0
co = n
p = 0
while co-B[p][0]>=0 :
    ans += B[p][1] * B[p][0]
    co -= B[p][0]
    p += 1
    #print(co)
print(ans + co * B[p][1])


Measured memory_bytes: 44996
#include <iostream>

using namespace std;

int main()
{
	long long a, b;
	cin >> a >> b;

	if (a % 2 == 0) {
		if (b % 2 == 0) {
			cout << (b ^ ((b - a) / 2 % 2)) << endl;
		} else {
			cout << (b - a + 1) / 2 % 2 << endl;
		}
	} else {
		if (b % 2 == 0) {
			cout << (((b - a - 1) / 2 % 2) ^ a ^ b) << endl;
		} else {
			cout << (a ^ ((b - a) / 2 % 2)) << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


union = UnionFind(N-1)

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, d = map(int, input().split())
    graph[a-1].append((d, b-1))
    graph[b-1].append((-d, a-1))
    union.Unite(a-1, b-1)

roots = set()
for i in range(N):
    roots.add(union.Find_Root(i))

NUM = [None for _ in range(N)]
checked = [False for _ in range(N)]

def dfs(p, NUM, ans):
    x = NUM[p]
    for d, q in graph[p]:
        #print(p, q, NUM, d, x)
        if NUM[q] is None:
            NUM[q] = x+d
        elif NUM[q] != x+d:
            #print("different!!")
            ans = False
            return ans
        if checked[q]:
            continue
        checked[q] = True
        ans = dfs(q, NUM, ans)
    return ans

ans = True
for r in roots:
    NUM[r] = 0
    ok = dfs(r, NUM, True)
    ans = ans and ok

if ans:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 131224
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int m, n;

typedef int Weight;
typedef int Flow;
struct Edge {
	int src, dest, rev;
	Flow cap;
	Weight cost;
	bool operator < (const Edge &rhs) const
	{
		return cost > rhs.cost;
	}
	Edge(int s, int d) : src(s), dest(d) { ; }
	Edge(int s, int d, int c) : src(s), dest(d), cost(c) { ; }
	Edge(int s, int d, int r, Flow cp, Weight cst) : src(s), dest(d), rev(r), cap(cp), cost(cst) { ; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
void add_edge(Graph &g, int src, int dest, Flow cap)
{
	g[src].push_back(Edge{ src, dest, (int)g[dest].size(), cap, 0 });
	g[dest].push_back(Edge{ dest, src, (int)g[src].size() - 1, 0, 0 });
}

void add_edge(Graph &g, int from, int to, Flow cap, Weight cost)
{
	g[from].push_back(Edge(from, to, (int)g[to].size(), cap, cost));
	g[to].push_back(Edge(to, from, (int)g[from].size() - 1, 0, -cost));
}

Flow dfs(Graph &g, vector<bool> &used, int v, int t, Flow f)
{
	if (v == t) return f;
	used[v] = true;
	for (Edge& e : g[v])
	{
		if (!used[e.dest] && e.cap > 0)
		{
			Flow d = dfs(g, used, e.dest, t, min(f, e.cap));
			if (d > 0)
			{
				e.cap -= d;
				g[e.dest][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

Flow ford_fulkerson(Graph &g, int s, int t)
{
	Flow flow = 0;
	for (;;)
	{
		vector<bool> used(g.size(), false);
		Flow f = dfs(g, used, s, t, INF);
		if (f == 0) return flow;
		flow += f;
	}
}

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

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	while (cin >> m >> n, m)
	{
		Graph g(m + n + 2);
		int src = m + n, sink = m + n + 1;
		REP(i, m) add_edge(g, src, i, 1);
		REP(i, n) add_edge(g, i + m, sink, 1);
		vi a(m), b(n);
		REP(i, m) cin >> a[i];
		REP(i, n) cin >> b[i];
		REP(i, m)REP(j, n)
		{
			if (gcd(a[i], b[j]) != 1) add_edge(g, i, j + m, 1);
		}
		cout << ford_fulkerson(g, src, sink) << endl;
	}
	return 0;
}

Measured memory_bytes: 10144
#include <stdio.h>

int main(void) {
  int a, b;

  while (scanf("%d %d", &a, &b) != EOF) {
    int sum = a+b;
    int count = 0;

    while (sum>0) {
      sum /= 10;
      count++;
    }

    printf("%d\n", count);
  }

  return 0;
}     
      

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.size();
    if (s == t.substr(0, n)) cout << "Yes" << en;
    else cout << "No" << en;
    return;
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}


Measured memory_bytes: 3596
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            long iA = long.Parse(sS[0]);
            long iB = long.Parse(sS[1]);
            long iK = long.Parse(sS[2]);

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            iA -= iK; 
            if (iA < 0)
            {
                iB += iA;
                iA = 0;
                if (iB < 0)
                {
                    iB = 0;
                }
            }
            string sOut = iA.ToString() + " " + iB.ToString();

            // 出力
            System.Console.WriteLine("{0}", sOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


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

using namespace std;

using ll = long long;
const int N = (int)2e5 + 5, LOG = 61;
int n, a[N], nxt[N][LOG];
ll cost[N][LOG];
bool ex[N];
map<int, int> lst;
vector<int> ans;
ll K;

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

//    freopen("test.INP", "r", stdin);

    cin >> n >> K; --K;
    for (int i = 0; i < n; ++i) cin >> a[i];

    for (int i = n - 1; i >= 0; --i) {
        if (lst.count(a[i]) ) nxt[i][0] = lst[ a[i] ];
        else nxt[i][0] = -1;
        lst[ a[i] ] = i;
    }

    for (int i = 0; i < n; ++i) {
        if (nxt[i][0] == -1) nxt[i][0] = lst[ a[i] ];
        if (nxt[i][0] <= i) cost[i][0] = 1;
    }

    for (int j = 1; j < LOG; ++j) {
        for (int i = 0; i < n; ++i) {
            nxt[i][j] = nxt[ (nxt[i][j - 1] + 1) % n ][j - 1];
            cost[i][j] = cost[i][j - 1] + cost[ (nxt[i][j - 1] + 1) % n ][j - 1] + (nxt[i][j - 1] == n - 1);
        }
    }

    int cur = 0;
    for (int i = LOG - 1; i >= 0; --i) if (cost[cur][i] <= K) {
        K -= cost[cur][i];
        cur = nxt[cur][i];
        if (cur == n - 1) --K;
        cur = (cur + 1) % n;
    }

    if (K < 0) return 0;

    for (int i = cur; i < n; ++i) {
        if (ex[ a[i] ]) {
            while (ans.back() != a[i]) {
                ex[ans.back()] = 0;
                ans.pop_back();
            }
            ex[ans.back()] = 0;
            ans.pop_back();
        }
        else {
            ans.push_back(a[i]);
            ex[ a[i] ] = 1;
        }
    }

    for (int _ : ans) cout << _ << ' '; cout << '\n';

    return 0;
}



Measured memory_bytes: 155764
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

#define MAX_N 1000010
ll inv[MAX_N+10],fac[MAX_N+10],ifac[MAX_N+10];

void setComb(){
  inv[0]=1;inv[1]=1;fac[1]=1;ifac[1]=1;fac[0]=1;ifac[0]=1;
  for(int i=2;i<MAX_N;i++){
    inv[i]=(-MOD/i)*inv[MOD%i]%MOD;
    fac[i]=fac[i-1]*i%MOD;
    ifac[i]=ifac[i-1]*inv[i]%MOD;

    inv[i]=(inv[i]+MOD)%MOD;
    fac[i]=(fac[i]+MOD)%MOD;
    ifac[i]=(ifac[i]+MOD)%MOD;
  }
  return;
}

ll comb(ll n,ll k){
  if(n<k||n<0||k<0) return 0;
  else return ((fac[n]*ifac[k]%MOD*ifac[n-k]%MOD+MOD)%MOD);
}

ll hcomb(ll n,ll r){// this size is really ok??
  if(n==0&&r==0) return 1;
  else if(n<0||r<0) return 0;
  else return comb(n+r-1,r);
}

ll mod_pow(ll x,ll n){
  x%=MOD;
  ll res=1;
  while(n>0){
    if(n&1) res=res*x%MOD;
    x=x*x%MOD;
    n>>=1;
  }
  return res;
}

void add(ll &a,ll b){
  a=(a+b)%MOD;
}

void mul(ll &a,ll b){
  a%=MOD;b%=MOD;
  a=a*b%MOD;
}

int N;
vector<vector<int>> g;

vector<ll> dp;
vector<ll> size;

void sizedfs(int now,int par){
    size[now]=1;
    for(auto nex:g[now]) if(nex!=par){
        sizedfs(nex,now);
        size[now]+=size[nex];
    }
}

void preset(int now,int par){
    ll sum=size[now]-1;
    if(sum==0){
        dp[now]=1;
        return;
    }

    ll ans=1;
    for(auto nex:g[now]) if(nex!=par){
        preset(nex,now);
        mul(ans,dp[nex]);
        mul(ans,comb(sum,size[nex]));
        sum-=size[nex];
    }
    dp[now]=ans;
}

vector<ll> result;

void dfs(int now,int par,ll pval){
    result[now]=dp[now];
    mul(result[now],pval);
    mul(result[now],comb(N-1,N-size[now]));

    for(auto nex:g[now]) if(nex!=par){
        ll iv=mod_pow(dp[nex],MOD-2);
        mul(iv,mod_pow(comb(N-1,size[nex]),MOD-2));
        mul(iv,result[now]);
        dfs(nex,now,iv);
    }
}

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

  cin>>N;
  g.resize(N);
  rep(i,N-1){
      int a,b;
      cin>>a>>b;
      a--;b--;
      g[a].push_back(b);
      g[b].push_back(a);
  }

  setComb();

  size.resize(N,0);
  sizedfs(0,-1);

  dp.resize(N,0);
  preset(0,-1);

  result.resize(N,0);
  dfs(0,-1,1);

  rep(i,N) cout<<result[i]<<endl;

  return 0;
}


Measured memory_bytes: 42100
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define pb          push_back
#define mp          make_pair
#define mt          make_tuple
#define get0(x)     (get<0>(x))
#define get1(x)     (get<1>(x))
#define get2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       9223372036854775807LL
#define LLMIN       -9223372036854775808LL
#define IMAX        2147483647
#define IMIN        -2147483648
typedef long long LL;
using namespace std;
typedef vector<pair<int,int> > vp;

vector<pair<int,int> > primeFactor(int num){ //first->prime,second->pow{
    if(num==1){
        vector<pair<int,int> > r;
        r.push_back(make_pair(1,1));
        return r;
    }
    else{
        vector<pair<int,int> > r;
        for(int i=2;i*i<=num;i++){
            if(num%i==0){
                int p=0;
                while(num%i==0)
                    num/=i,p++;
                r.push_back(make_pair(i,p));
            }
        }
        if(num!=1)
            r.push_back(make_pair(num,1));
        return r;
    }
}

LL mod = 1e9+7;

int main(void){
    int N;
    cin>>N;
    map<int,int> ma;
    FOR(i,2,N+1){
        auto pf = primeFactor(i);
        REP(i,SZ(pf)){
            auto p = pf[i];
            // printf("p.first=%d p.second=%d\n",p.first,p.second);
            ma[p.first]+=p.second;
        }
    }
    LL ans=1;
    for(auto it=ma.begin();it!=ma.end();it++){
        ans*=((*it).second+1);
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

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

ll gcd(ll a, ll b) { //最大公約数
    if (a%b == 0) return b;
    else return gcd(b,a%b);
}

int main() {
    int n,x;
    cin>>n>>x;
    vector<int> X(n);
    ll ans;
    rep(i,n) {
        cin>>X[i];
        X[i]=abs(X[i]-x);
    }
    ans=X[0];
    for (int i=1; i<n; i++) {
        ans=gcd(ans,X[i]);
    }
    cout<<ans<<endl;
}   


Measured memory_bytes: 640
#include<iostream>
#include<queue>

using namespace std;

#define rep(i, n) for (int i = 0; i < int(n); ++i)

bool valid(int n) {return 0 <= n && n < 1024;}
bool valid(string str) {
  int t = 0;
  rep (i, str.size()) {
    if (str[i] == '(') ++t;
    if (str[i] == ')') {
      --t;
      if (t < 0) return false;
    }
  }
  return t == 0;
}

int num(string str) {
  int n = 0;
  rep (i, str.size()) {
    n = n * 2 + str[i] - '0';
    if (n >= 1024) throw 1;
  }
  return n;
}

int exp1(string str);
int exp2(string str);
int exp3(string str);

int exp1(string str) {
  if (str.size() == 0u) throw 1;
  int t = 0, n = str.size(), s = 0;
  vector<int> v;
  rep (i, n) {
    if (str[i] == '(') ++t;
    if (str[i] == ')') {
      --t;
      if (t < 0) throw 1;
    }
    if (t == 0 && (str[i] == '+' || str[i] == '-')) {
      v.push_back((s == 0 || str[s - 1] == '+' ? 1 : -1) * exp1(str.substr(s, i - s)));
      s = i + 1;
    }
  }
  if (t != 0) throw 1;
  if (v.size() == 0u) return exp2(str);
  v.push_back((s == 0 || str[s - 1] == '+' ? 1 : -1) * exp1(str.substr(s, n - s)));
  int res = 0;
  rep (i, v.size()) {
    res += v[i];
    if (!valid(res)) throw 1;
  }
  return res;
}

int exp2(string str) {
  if (str.size() == 0u) throw 1;
  int t = 0, n = str.size(), s = 0;
  vector<int> v;
  rep (i, n) {
    if (str[i] == '(') ++t;
    if (str[i] == ')') {
      --t;
      if (t < 0) throw 1;
    }
    if (t == 0 && str[i] == '*') {
      v.push_back(exp1(str.substr(s, i - s)));
      s = i + 1;
    }
  }
  if (t != 0) throw 1;
  if (v.size() == 0u) return exp3(str);
  v.push_back(exp1(str.substr(s, n - s)));
  int res = 1;
  rep (i, v.size()) {
    res *= v[i];
    if (!valid(res)) throw 1;
  }
  return res;
}

int exp3(string str) {
  if (str.size() == 0u) throw 1;
  int t = 0, n = str.size();
  bool f = true;
  rep (i, n) if (!isdigit(str[i])) f = false;
  if (f) return num(str);
  if (str[0] != '(' || str[n - 1] != ')') throw 1;
  str = str.substr(1, n - 2);
  vector<int> v;
  rep (i, n) {
    if (str[i] == '(') ++t;
    if (str[i] == ')') {
      --t;
      if (t < 0) throw 1;
    }
    if (t == 0 && (str[i] == '+' || str[i] == '-' || str[i] == '*')) {
      return exp1(str);
    }
  }
  throw 1;
}

const char c[] = {'0', '1', '+', '-', '*', '(', ')'};
int solve0(string str, vector<int> dot) {
  if (dot.size() == 0u) {
    try {
      //cout << str << " " << exp1(str) << endl;
      return exp1(str);
    } catch(int n) {
      return -1;
    }
  }
  int n = dot.back();
  dot.pop_back();
  int res = -1;
  rep (i, 7) {
    str[n] = c[i];
    res = max(res, solve0(str, dot));
  }
  return res;
}

int main() {
  string str;
  cin >> str;
  vector<int> dot;
  rep (i, str.size()) if (str[i] == '.') dot.push_back(i);
  cout << solve0(str, dot) << endl;
  return 0;
}

Measured memory_bytes: 1288