akhauriyash/Code-Regression huggingface dataset:
n,m = map(int,input().split())
mod = m
# mod = 10**9+7

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

ini = 1

def calc(a,b):
    p = a * b % mod
    return p

# calc1 の定義
def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    p_num += 1
    dp1[c] = p_num % mod

# calc2 の定義
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append(calc(a,b))

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1)%mod



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = ini
for i in order:
    calc2(i)

for i in range(1,n+1):
    ans = calc(dp1[i]-1, dp2[i])
    print(ans)

Measured memory_bytes: 96212
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val N, M, K = Integer.parseInt(sc.next)

    for (i <- 0 to N) {
      for (j <- 0 to M) {
        if (i * M + j * N - 2 * i * j == K) {
          println("Yes")
          return
        }
      }
    }
    println("No")
  }
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    LL h,n;
    cin>>h>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=n-1;i>=0;i--){
        if(h>0){
            h=h-a[i];
        }
        else{
            break;
        }
    }
    if(h>0){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
}

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

int main () {
  char a;
  cin >> a;
  if (65 <= (int)a && (int)a <= 90) cout << "A" << endl;
  else cout << "a" << endl;
  return 0;
}

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

int main(){
	int N;
	cin >> N;
	cout << (N+1)/2 << endl;
    return 0;
}



Measured memory_bytes: 256
import math
import itertools


def main():
    N = int(input())
    P = list(input().split())
    Q = list(input().split())

    # n_iterals = math.factorial(N)
    # iterals = list(range(1, n_iterals+1))

    combinations = []
    for c in itertools.permutations(range(1, N+1), N):
        c_s = map(str, c)
        combinations.append("".join(c_s))

    a = combinations.index("".join(P))
    b = combinations.index("".join(Q))

    print(abs(a-b))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5940
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    S = input()

    if S == "RRR":
        print(3)
    elif S[1:3] == "RR" or S[0:2] == "RR":
        print(2)
    else:
        ans = 0
        for s in S:
            if s == "R":
                ans = 1
        print(ans)






if __name__ == "__main__":
    main()

Measured memory_bytes: 61748
H, W = map(int, input().split())
A = []
total = 0
for _ in range(H):
    row = list(map(int, input().split()))
    A.append(row)
    total += sum(row)

lines = []
for y in range(H - 1):
    for x in range(W):
        if A[y][x] % 2 == 1:
            lines.append(f'{y+1} {x+1} {y+2} {x+1}')
            A[y][x] -= 1
            A[y + 1][x] += 1
y = H - 1
for x in range(W - 1):
    if A[H - 1][x] % 2 == 1:
        lines.append(f'{y+1} {x+1} {y+1} {x+2}')
        A[y][x] -= 1
        A[y][x + 1] += 1
print(len(lines))
for line in lines:
    print(line)

Measured memory_bytes: 20452
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N, M;
    cin >> N >> M;

    vector<int> A, B;

    for(int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        A.push_back(a);
        B.push_back(b); 
    }

    vector<int> cnt(N, 0);

    for(int i = 0; i < M; i++)
    {
        cnt.at(A.at(i)-1)++;
        cnt.at(B.at(i)-1)++;
    }

    for(int i = 0; i < N; i++)
    {
        cout << cnt.at(i) << '\n';
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int a,b,c,x=0;
	cin>>a>>b>>c;
	for(int i=0;i<c;i++){
		if(b<a){
			cout<<x<<endl;
			return 0;
			}
		b=b-a;
		x++;
		}
		cout<<x<<endl;
		return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
                                                                                                                                     
long long mod = 1e9 + 7;

long long sum(long long high, long long low){
        return ((high-low+1) * (high+low) / 2); 
}

int main(){
        long long N, ans = 0, K;
        cin >> N >> K;

        for(int i = K; i <= N+1; ++i){
                long long max, min;
                max = sum(N, N - i + 1); 
                min = sum(i - 1, 0); 
                ans = ans + (max-min+1);
        }

        cout << ans % mod << endl;
        return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
long long int power(int a,int b)
{
    if(b==0)
        return 1;
    long long int k=power(a,b/2);
    if(b%2==0)
        return ((k%M)*(k%M))%M;
    else
        return ((k%M)*(k%M)*(a%M))%M;
}
long long int fact(long long int n)
{
    if(n==1 || n==0)
        return 1;
    else
        return ((n%M)*(fact(n-1)%M))%M;

}
int div(int n)
{  int c=0;
    for(int i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
          if(n/i==i)
            c++;
          else
            c+=2;
        }

    }

    
    return  c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifndef ONLINE_JUDGE
 
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
   #endif
   
   int n;
   cin>>n;
   int c=0;
   for(int i=1;i<=n;i+=2)
{
     if(div(i)==8)
        c++;
}
cout<<c;




 return 0;
}








Measured memory_bytes: 3596
/*
    if you can't see the repay
    Why not just work step by step
    rubbish is relaxed
    to WzW
*/


#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std ;

int main()
{
	int n;cin >> n;int a[120];
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	int ans = 0;int maxx= 1000000;
	for(int i = 1; i <= 100;i++){
		int cur = 0;
		for(int k = 1; k <= n;k++){
			cur += (a[k] - i) * (a[k] - i);
		}
		if(maxx > cur){
			maxx = cur;ans = i;
		}
	}
	printf("%d\n",maxx);
}
 

Measured memory_bytes: 256
function Main(input) {
	input = input.split("\n");
	var a = parseInt(input[0], 10);
	var b = parseInt(input[1], 10);
  	var c = a%500;
  	b >= c ? console.log('Yes') : console.log('No')
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main(){
    int n,k; cin>>n>>k;
    map<int,int> m;
    for(int i=0;i<n;i++){
        int a; cin>>a;
        m[a]++;
    }
    
    vector<pair<int,int>> p;
    for(auto q:m){
        p.push_back(make_pair(q.second,q.first));
    }
    sort(p.begin(),p.end());
    int ans=0,cnt=0;
    while(p.size()-cnt>k){
        ans+=p[cnt].first;
        cnt++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 11768
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int nPr(int n, int r) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++)
		sum *= i;
	return sum;
}
//int nCr1(int n, int r)
//int nCr2(int n, int r) 
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
inline bool PRIMEOR (int x) {
	if (x ==1)
		return false;
	if (x == 2)
		return true;
	if (x%2==0)
		return false;
	double sqrtx = sqrt(x);
	for (int i = 3; i <= sqrtx; i += 2) {
		if (x % i == 0)
			return false;
	}
	return true;
}

using namespace std;
#pragma endregion
signed main() {
	int A,B,C;
	cin >> A >> B >> C;
	if (BETWEEN(C,min(A,B),max(A,B)))
		cout << "Yes" << endl;
	else 
		cout << "No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll MOD=1000000007;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
long long gcd(long long a,long long b){
    ll gcdmax=max(a,b);
    ll gcdmin=min(a,b);
    while(true){
        if(gcdmax%gcdmin==0)break;
        else gcdmax%=gcdmin;
        swap(gcdmin,gcdmax);
    }
    return gcdmin;
}
ll powerup(ll N,ll P,ll M){
    if(P==0)return 1;
    else if(P%2==0){
        ll t=powerup(N,P/2,M);
        return t*t%M;
    }
    else return N*powerup(N,P-1,M)%M;
}
int main()
{
  ll N;
  cin>>N;
  vector<ll> A(N);
  rep(i,N) cin>>A.at(i);
  sort(A.begin(),A.end());
  rep(i,N){
    if(i>0)A.at(i)+=A.at(i-1);
  }
  reverse(A.begin(),A.end());
  ll ans;
  rep(i,N){
    if(i==0)ans=1;
    else if(A.at(i)*3>=A.at(i-1))ans++;
    else break;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define forever for (;;)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
template<typename A> using V = std::vector<A>;
template<typename A> using F = std::function<A>;
template<typename A, typename B> using P = std::pair<A, B>;
using pii = P<int, int>;
using vi = V<int>;
using vd = V<double>;
using vs = V<std::string>;
using vpii = V<pii>;
using vvi = V<vi>;
using vvpii = V<vpii>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> std::istream &operator>>(std::istream &is, std::pair<A, B> &p) { is >> p.first; is >> p.second; return is; }
using namespace std;
// clang-format on

main {
  int k;
  while (cin >> k, k) {
    vi c(k * (k - 1) / 2);
    cin >> c;
    cout << accumulate(all(c), 0) / (k - 1) << endl;
  }
}

Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

/*
考察
- 無限回の場合は簡単に場合分けできる
- それ以外のケースはシミュレーションをしたくなるが，それはTLEっぽい
- aとbが最後に会う時間を求めれば良い気がする -> 2分探索?
- 分からん！解説を見る
*/

int main(){
    ll t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    ll p = a1 * t1 - b1 * t1;
    ll q = a2 * t2 - b2 * t2;
    if(p > 0){
        p = -p;
        q = -q;
    }
    if(p + q == 0){
        cout << "infinity" << endl;
    }else if(p + q < 0){
        cout << 0 << endl;
    }else{
        ll s = (-p) / (p+q);
        ll t = (-p) % (p+q);
        if(t == 0) cout << 2 * s << endl;
        else cout << 2 * s + 1 << endl;
    }
    return 0;
}

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

#define INF (INT32_MAX/2)
#define MOD (1000000000+7)
#define MAX 300

int N;
int a[MAX];

int d[4];
double dp[MAX + 1][MAX + 1][MAX + 1];

int main() {
	cin >> N;
	for( int i = 0; i < N; i++ ) {
		cin >> a[i];
		d[a[i]]++;
	}

	for( int i = 0; i <= N; i++ ) {
		for( int j = 0; j <= N; j++ ) {
			for( int k = 0; k <= N; k++ ) {
				if( i == 0 && j == 0 && k == 0 ) {
					continue;
				}
				if( i + j + k > N ) {
					break;
				}
				double p = 0;
				if( i > 0 ) {
					p += i * dp[i - 1][j + 1][k];
				}
				if( j > 0 ) {
					p += j * dp[i][j - 1][k + 1];
				}
				if( k > 0 ) {
					p += k * dp[i][j][k - 1];
				}
				int eat = i + j + k;
				dp[i][j][k] = p / eat + (double)N / eat;
			}
		}
	}

	double ans = dp[ d[3] ][ d[2] ][ d[1] ];

	cout << fixed << setprecision(10) << ans << endl;

	return 0;
}


Measured memory_bytes: 213248
import sys,bisect
input = sys.stdin.readline
n,m = map(int,input().split())
edge = [[] for i in range(n)]

#st: 今考えている辺の中で入る辺が無い頂点
st = []
#to[i]: 今考えている辺の中で頂点iに入る辺数
to = [0]*n
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    to[y-1] += 1
for i in range(n):
    if to[i] == 0:
        st.append(i)

#dp[i]: 頂点iを終点とする最長のパスの長さ
dp = [0]*n
while len(st):
    go = st.pop()
    for e in edge[go]:
        to[e] -= 1
        if to[e] == 0:
            st.append(e)
        dp[e] = max(dp[e],dp[go]+1)
print(max(dp))


Measured memory_bytes: 56880
import math

a, b = map(int, input().split())

if a == b:
    print((2 * math.factorial(a) * math.factorial(b)) % 1000000007)
elif abs(a-b) == 1:
    print((math.factorial(a)*math.factorial(b)) % 1000000007)
else:
    print(0)


Measured memory_bytes: 5192
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  auto start = clock();
  Int h,w;
  cin>>h>>w;
  vector<string> s(h);
  for(Int i=0;i<h;i++) cin>>s[i];

  auto YES=[&](){
    cout<<"YES"<<endl;
    exit(0);
  };

  auto calc=[&](string s){
    Int res=0;
    for(Int i=0;i<(Int)s.size();i++)
      res=res*26+(s[i]-'a');
    return res;
  };

  
    
  for(Int c=0;c<(w&1?w:1LL);c++){
    if(w&1){
      map<char,Int> mc;
      for(Int i=0;i<h;i++) mc[s[i][c]]++; 
      Int odd=0;
      for(auto p:mc) odd+=p.second&1;
      if(h%2==0&&odd>0) continue;
      if(h%2==1&&odd>1) continue;
    }
    Int bit=(1<<((w+1)/2))-1;
    while(bit<(1<<w)){
      //cout<<bit<<endl;
      if((w&1) && !((bit>>c)&1)){
	Int x=bit&-bit,y=bit+x;
	bit=((bit&~y)/x>>1)|y;
	continue;
      }
      
      vector<Int> x,y;
      for(Int j=0;j<w;j++){
	if((w&1) && c==j) continue;
	if((bit>>j)&1) x.emplace_back(j);
	else y.emplace_back(j);
      }      
      assert(x.size()==y.size());
      
      do{
	using P = pair<Int, Int>;
	map<P, Int> mp;
	for(Int i=0;i<h;i++){
	  string a,b;
	  for(Int j=0;j<(Int)x.size();j++){
	    a+=s[i][x[j]];
	    b+=s[i][y[j]];
	  }
	  if(w&1){
	    a+=s[i][c];
	    b+=s[i][c];
	  }
	  mp[P(calc(a),calc(b))]++;
	}	  
	auto rev=[&](P p){return P(p.second,p.first);};
	auto ch=mp;
	Int flg=1,cnt=0;
	for(auto p:mp){
	  flg&=ch[p.first]==ch[rev(p.first)];
	  cnt+=(p.first.first==p.first.second)*(p.second&1);
	}
	if(flg && ((h&1) == cnt) ) YES();
      }while(next_permutation(y.begin(),y.end()));	   

      if((double)(clock()-start)/CLOCKS_PER_SEC>1.95){
	cout<<"NO"<<endl;
	return 0;
      }
      
      {
	Int x=bit&-bit,y=bit+x;
	bit=((bit&~y)/x>>1)|y;
      }
    }
  }
  cout<<"NO"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int x,y,r=1;
  int v;
  scanf("%d%d",&x,&y);
  if(y>x){
    v=x;
    x=y;
    y=v;
  }
  while(r!=0){
    r=x%y;
    x=y;
    if(r!=0){
    y=r;
    }
  }
  printf("%d\n",y);
  return 0;
}

Measured memory_bytes: 1020
#  --*-coding:utf-8-*--

def f(W):
    l = 0
    r = sum(W)
    d = r

    for w in W:
        l += w
        r -= w
        
        d2 = abs(l-r)

        if d2 < d:
            d = d2

    return d



def main():
    N = int(input())
    W = list(map(int, input().split()))
    print(f(W))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <queue>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
    int n;
    cin >> n;
    vector<int> ans(4);
    rep(i, n) {
        string in;
        cin >> in;
        if (in == "AC") ans[0]++;
        else if (in == "WA") ans[1]++;
        else if (in == "TLE") ans[2]++;
        else if (in == "RE") ans[3]++;
    }

    cout << "AC x " << ans[0] << endl;
    cout << "WA x " << ans[1] << endl;
    cout << "TLE x " << ans[2] << endl;
    cout << "RE x " << ans[3] << endl;

}


Measured memory_bytes: 3632
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s1 = sc.nextLine().split(" ");
        BigDecimal w=new BigDecimal( s1[0] );
        BigDecimal h=new BigDecimal( s1[1] );
        BigDecimal x=new BigDecimal( s1[2] );
        BigDecimal y=new BigDecimal( s1[3] );

        BigDecimal bd = w.multiply(h).divide(new BigDecimal(2));
        BigDecimal menseki=bd.setScale(9, BigDecimal.ROUND_DOWN);
        int judge=0;
        if (x.compareTo(w.divide(new BigDecimal(2)))==0 && y.compareTo(h.divide(new BigDecimal(2)))==0) {
        	judge=1;
        }

        System.out.println(menseki + " " + judge);
    }
}

Measured memory_bytes: 22868
package main

import (
	"fmt"
)

func main() {
	var x1, y1, x2, y2 int
	fmt.Scanf("%d%d%d%d", &x1, &y1, &x2, &y2)
	var x3, y3, x4, y4 int
	x3 = x2 - (y2 - y1)
	y3 = y2 + (x2 - x1)
	x4 = x3 - (x2 - x1)
	y4 = y3 - (y2 - y1)
	fmt.Printf("%d %d %d %d\n", x3, y3, x4, y4)
}


Measured memory_bytes: 512
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <utility>
#include <set>
#include <random>
#include <map>
#include <stack>
#include <queue>
#include <list>
#include <functional>
#define LL long long


using namespace std;

int main() {
    int n;
    LL t;
    cin >> n >> t;
    LL X = 0;
    LL water_start;
    LL water_end;
    vector<int> vt(n);
    for (size_t i = 0; i < n; i++)
    {
        cin >> vt[i];
    }
    for (size_t i = 0; i < n; i++)
    {
        if (i == 0)
        {
            X += vt[0];
            water_start = 0;
            water_end = t;

            if (i == n - 1)
            {
                X += water_end - water_start;
            }
        }
        else
        {
            if (vt[i] < water_end)
            {
                water_end = vt[i] + t;
            }
            else
            {
                X += water_end - water_start;
                water_start = vt[i];
                water_end = vt[i] + t;
            }

            if (i == n - 1)
            {
                X += water_end - water_start;
            }
        }
    }
    cout << X << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
long long a, b, c;
long long gcd (long long x, long long y) {
	if (x < y) swap(x, y);
	while (x % y) {
		long long r = x % y;
		x = y, y = r;
	}
	return y;
}
int main () {
	scanf("%lld%lld", &a, &b);
	c = gcd(a, b);
	int ans = 1;
	for (long long i = 2; i * i <= c; i++) {
		if (c % i == 0) {
			ans++;
			while (c % i == 0) c /= i;
		}
	}
	if  (c > 1) ans++;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define END return 0
typedef int64_t ll;
const int mod7 = 1e9 + 7;
const int mod9 = 1e9 + 9;
const int inf = 1 << 30;
const ll INF = 1LL << 60;
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a % b) : abs(a);}
template<typename T> T lcm(T a, T b) {return a / gcd(a, b) * b;}
template<typename T> bool chmax(T &a, T b) {if (a < b) {a = b; return true;} return false;}
template<typename T> bool chmin(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) {fill((T*)array, (T*)(array+N), val);}

int main() {
    int n, m;
    cin >> n >> m;
    if(n == m) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
s=input()

#0はじまりの場合
ans_0=0
count=0
for i in s:
    if int(i) != count % 2: ans_0+=1
    count+=1

#1はじまりの場合
ans_1=0
count=1
for i in s:
    if int(i) != count %2: ans_1+=1
    count+=1

print(min(ans_0,ans_1))

Measured memory_bytes: 9292
//       In the name of         ****                      God                     ****

/*

Copyright (C)          JadedBeast

                                   Morocco

created : 8/3/2019

*/

#include <bits/stdc++.h>
using namespace std;
#define time cout << "\ntime: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;

    




int main(void){
	int n,k;
    cin >> n  ;
    int DP[n],v[n];
    fill(DP,DP+n,INT_MAX);
    for(int i =0 ;i<n ;i++)
        cin >> v[i];
    DP[0]=0;
    for (int i = 0; i <n-1; ++i)
    {	

   		DP[i+1]=min(DP[i]+abs(v[i]-v[i+1]),DP[i+1]);
   		if(i<n-2)
   			DP[i+2]=min(DP[i]+abs(v[i]-v[i+2]),DP[i+2]);
    }
    cout << DP[n-1]<<endl;

   return 0;
}


Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using static System.Console;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        solve();
    }
    static int N;
    static int[] A;
    static void input()
    {
        N = int.Parse(ReadLine());
        A = new int[N];
        for(int i = 0; i < N; i++)
        {
            A[i] = int.Parse(ReadLine());
        }
    }
    static void solve()
    {
        input();
        int max = 0;
        int subMax = 0;
        int maxIndex = 0;

        for (int i = 0; i < N; i++)
        {
            if(A[i] >= max)
            {
                subMax = max;
                max = A[i];
                maxIndex = i;
            }
            else
            {
                subMax = Max(A[i], subMax);
            }
        }

        for(int i = 0; i < N; i++)
        {
            if (maxIndex == i)
                WriteLine(subMax);
            else
                WriteLine(max);
        }
    }
}

Measured memory_bytes: 19400
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[2000010];
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
void init_fact(){
    kaijo[0]=1;
    for(int i=1;i<=2000000;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    if(!kaijo[0])init_fact();
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}
int n;
vector<int>v[100010];
bool used[100010];
int G[100010];
void dfs(int x){
    used[x]=true;
    for(int i:v[x]){
        if(!used[i]){
            dfs(i);
            G[x]^=(G[i]+1);
        }
    }
}
signed main(){
    cin>>n;
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        a--,b--;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(0);
    if(G[0]==0)puts("Bob");
    else puts("Alice");
    return 0;
}


Measured memory_bytes: 12160
#include <iostream>
#include <string>

using namespace std;

int main() {
	int N;
	cin >> N;
	string S;
	cin >> S;
	
	int brackets[] = {0 , 0};
	for (int i = 0; i < N; ++i) {
		if (S[i] == ')') {
			if (brackets[0] == 0) {
				brackets[1] += 1;
			} else {
				brackets[0] -= 1;
			}
		} else {
			brackets[0] += 1;
		}
	}
	
	for (int i = 0; i < brackets[1]; ++i) {
		cout << "(";
	}
	cout << S;
	for (int i = 0; i < brackets[0]; ++i) {
		cout << ")";
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

ll dp[203][100003];

int main()
{
    ll n, x;
    cin >> n >> x;
    ll s[203];
    for(int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n, greater<ll>());
    dp[0][x] = 1;
    for(ll i = 1; i <= n; i++) dp[0][x] = dp[0][x] * i % MOD;
    for(int i = 0; i < n; i++){
        ll r = modpow(n - i, MOD - 2);
        for(int j = 0; j <= x; j++){
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (n - i - 1) % MOD * r) % MOD;
            dp[i + 1][j % s[i]] = (dp[i + 1][j % s[i]] + dp[i][j] * r) % MOD;
        }
    }
    ll ans = 0;
    for(int j = 0; j <= x; j++) ans = (ans + dp[n][j] * j) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 157184
#include<stdio.h>
int main() {
    int n, i, a, b,  q = 0, w = 0, e = 0, ans,p;
    scanf("%d%d%d", &n, &a, &b);
    for (i = 0; i < n; i++) {
        scanf("%d", &p);
        if (p <= a)
            q++;
        else if (p <= b)
            w++;
        else
            e++;
    }
    ans = q;
    if (ans > w)
        ans = w;
    if (ans > e)
        ans = e;
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
ll N, S, X[100500], P[100500];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> S;
    for(int i = 1; i <= N; i++) cin >> X[i] >> P[i];
    vector<l_l> before;
    vector<l_l> after;
    for(int i = 1; i <= N; i++) {
        if(X[i] >= S) break;
        before.push_back({X[i], P[i]});
    }
    for(int i = N; i >= 1; i--) {
        if(X[i] <= S) break;
        after.push_back({X[i], P[i]});
    }
    ll sum = 0;
    int cheer = 1;
    vector<l_l> que;
    int after_index = 0;
    int before_index = 0;
    for(int time = 1; time <= N; time++) {
        if(after_index >= after.size()) {
            que.push_back(before[before_index]);
            before_index++;
            continue;
        }
        if(before_index >= before.size()) {
            que.push_back(after[after_index]);
            after_index++;
            continue;
        }
        ll left = before[before_index].second;
        ll right = after[after_index].second;
        if(cheer == 1) {
            left += sum;
        } else {
            right += sum;
        }
        if(right > left) {
            que.push_back(before[before_index]);
            sum += before[before_index].second;
            before_index++;
            cheer = 0;
        } else {
            que.push_back(after[after_index]);
            sum += after[after_index].second;
            after_index++;
            cheer = 1;
        }
    }
    ll ans = 0;
    ll now = S;
    for(int i = que.size() - 1; i >= 0; i--) {
        ans += abs(que[i].first - now);
        now = que[i].first;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<cstdlib>
#define pb push_back
#define mk make_pair
#define ll long long
#define lson ch[x][0]
#define rson ch[x][1]

using namespace std;

inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
   while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
   return x*f;
}

int in[10];

int main()
{
   for (int i=1;i<=3;i++) 
   {
    int x=read(),y=read();
    in[x]++;
    in[y]++;
   }
   int num1=0;
   for (int i=1;i<=4;i++) if (in[i]==1) num1++;
   if (num1==2) cout<<"YES";
   else cout<<"NO";
   return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

int main(){
	int phrases[3];
	for(int i = 0;i < 3;i++){
		cin >> phrases[i];
	}
	int five = 0,seven = 0;
	for(int i = 0;i < 3;i++){
		if(phrases[i] == 5) five++;
		if(phrases[i] == 7) seven++;
	}
	if(five == 2 && seven == 1)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    int n;cin>>n;
    ll res=0;
    for(int i=0;i<n;i++){
        ll a;cin>>a;
        while(a%2==0){
            res++;
            a/=2;
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, ans;
    scanf("%d", &n);
    ans = 0;
    for(int x, i = 0; i < n; i++)
    {
        scanf("%d", &x);
        if(x & 1) ans ^= 1;
    }
    if(ans) puts("NO");
    else
        puts("YES");
    return 0;
}


Measured memory_bytes: 256
from collections import deque
from itertools import repeat

MOD = 10**9 + 7

N,M = map(int,input().split())
S = tuple(map(int,input().split()))
T = tuple(map(int,input().split()))

if N < M:
    N,M = M,N
    S,T = T,S

dp = deque(repeat(1, M+1), M+2)


for s in S:
    dp.append(1)
    for t in T:
        if s == t:
            dp.append(dp[1]+dp[-1])
        else:
            dp.append(dp[1]-dp[0]+dp[-1])

print(dp[-1]%MOD)

Measured memory_bytes: 4468
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    try(Scanner sc = new Scanner(System.in)){
      String line = sc.nextLine();
      String answer = "";
      int length = line.length();
      for(int i=0;i<length;i++){
        char ch = line.charAt(i);
        char a;
        if(Character.isLowerCase(ch)){
          a = Character.toUpperCase(ch);
        }else{
          a = Character.toLowerCase(ch);
        }
        answer += a;
      }
      System.out.println(answer);
    }
  }
}



Measured memory_bytes: 31412
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
#define pb push_back
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; }


int main() {
    cin.tie(0);    
	ios::sync_with_stdio(false);
    double W,H,x,y;
    cin >> W >> H >> x >> y;
    int ans = 0;
    if(W/2 == x && H/2 == y){
        ans = 1;
    }

    cout << (W*H)/2 << ' ' << ans << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>

using namespace std;

const int INF = 1e9 + 5;
const int nax = 1e5 + 5;
vector<int> g[nax];

void dfs(int s ,vector<int> &in_degree ,vector<bool> &visited ,vector<int> &dist) {
	assert(!visited[s]);
	visited[s] = true; 
	for(int n : g[s]) {
		dist[n] = max(dist[n] ,dist[s]+1);
		--in_degree[n];
		if(in_degree[n]==0) {
			dfs(n, in_degree ,visited ,dist);
		}
	}
}

int main() {
	int n ,m;
	int a ,b;
	cin >> n >> m;
	vector<int> dist(n+1);
	vector<bool> visited(n+1 ,false);
	vector<int> in_degree(n+1);
	while(m--) {
		cin >> a >> b;
		g[a].push_back(b);
		++in_degree[b];
	}
	int max =0;
	for(int i=1; i<=n; i++) {
		if(!visited[i] && in_degree[i] == 0) {
			dfs(i ,in_degree ,visited ,dist);
		}
	}
	for (int x : dist) {
		if(max < x) {
			max = x;
		}
	}
	cout << max;
	return 0;
}





















Measured memory_bytes: 12800
#include<bits/stdc++.h>
#define ll long long

const int N = 10010;

int n, m;
std::vector <std::pair <int, ll>> e[N];
ll dis[N] = {};
int cnt[N] = {};
bool inque[N] = {};

void spfa(int s){
	std::queue <int> q;
	for(int i = 1; i <= n; ++ i) dis[i] = LLONG_MAX;
	dis[s] = 0;
	q.push(s);
	inque[s] = true;
	cnt[s] = 1;
	while (!q.empty()){
		int u = q.front();
		q.pop();
		inque[u] = false;
		for (auto v : e[u]){
			if (dis[v.first] > dis[u] + v.second){
				dis[v.first] = dis[u] + v.second;
				if (!inque[v.first]){
					++ cnt[v.first];
					if (cnt[v.first] > 2 * n){
						return;
					}
					q.push(v.first);
					inque[v.first] = true;
				}
			}
		}
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 0, u, v; i < m; ++ i){
		ll c;
		scanf("%d%d%lld", &u, &v, &c);
		e[u].push_back({v, -c});
	}
	spfa(1);
	if (dis[n] == LLONG_MAX){
		assert(0 == 1);
	}
	if (cnt[n] > n){
		return printf("inf\n"), 0;
	}
	return printf("%lld\n", -dis[n]), 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<char> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
  }
  int P=0,W=0,G=0,Y=0;
  for (int i = 0; i < N; i++) {
    if(S.at(i)=='P') P=1;
    else if(S.at(i)=='W') W=1;
    else if(S.at(i)=='G') G=1;
    else Y=1;
  }
  if((P+W+G+Y)==4) cout << "Four" << endl;
  else cout << "Three" << endl;
}


Measured memory_bytes: 256
dish = []
for i in range(5):
    dish.append(int(input()))
tmp1 = sum([d // 10 + (d % 10 > 0) for d in dish]) * 10
tmp2 = sum(sorted([d % 10 for d in dish if d % 10 > 0])[:1])
if tmp2 > 0:
    print(tmp1 + tmp2 - 10)
else:
    print(tmp1)

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    s = input()
    a = int(s[0:2])
    b = int(s[2:4])
    dump(a,b)

    if (1 <= a <= 12 and 1 <= b <= 12):
        print("AMBIGUOUS")
    elif (1 <= a <= 12):
        print("MMYY")
    elif (1 <= b <= 12):
        print("YYMM")
    else:
        print("NA")

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}


Measured memory_bytes: 105068
import bisect
n=int(input())
l=list(map(int, input().split()))
l.sort()

count=0
for i in range(n-2):
	for j in range(i+1,n-1):
		maxk=bisect.bisect_left(l,l[i]+l[j],j+1,n)-1
		count+=maxk-j
print(count)

Measured memory_bytes: 3188
n=int(input())
s=list(input())
for i in range(n-1):
    t=[]
    p=list(input())
    for i in range(len(s)):
        if s[i] in p:
            t.append(s[i])
            p.pop(p.index(s[i]))
    else:
        s=t[:]
s.sort()
c=""
for i in range(len(s)):
    c+=s[i]
print(c)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using static Constans;

public static class Constans
{
    public const long Mod = (long)1e9 + 7;
}

public struct ModInt
{
    public long Num;

    public ModInt(long num)
    {
        Num = num;
    }

    public override string ToString()
    {
        return Num.ToString();
    }

    public static ModInt operator +(ModInt l, ModInt r)
    {
        l.Num += r.Num;
        if (l.Num >= Mod)
        {
            l.Num -= Mod;
        }
        return l;
    }

    public static ModInt operator -(ModInt l, ModInt r)
    {
        l.Num -= r.Num;
        if (l.Num < 0)
        {
            l.Num += Mod;
        }
        return l;
    }

    public static ModInt operator *(ModInt l, ModInt r)
    {
        return new ModInt(l.Num * r.Num % Mod);
    }

    public static implicit operator ModInt(long n)
    {
        n %= Mod;
        if (n < 0)
        {
            n += Mod;
        }
        return new ModInt(n);
    }
}

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = vals[0];
        var M = vals[1];
        var S = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var T = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var sum = new ModInt[N + 1, M + 1];
        for (int i = 0; i <= N; i++)
        {
            sum[i, 0] = 1;
        }
        for (int j = 0; j <= M; j++)
        {
            sum[0, j] = 1;
        }
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                sum[i, j] = sum[i - 1, j] + sum[i, j - 1];
                if (S[i - 1] != T[j - 1])
                {
                    sum[i, j] -= sum[i - 1, j - 1];
                }
            }
        }

        Console.WriteLine(sum[N, M]);
    }
}

Measured memory_bytes: 44640
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
double dp[3000]={1};
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    cout.precision(9);
    cout<<fixed;
    rep(i,n)
    {
        double p;
        cin>>p;
        for(int j=i+1;j>=0;j--)
        {
            dp[j]=(j==0?0:dp[j-1]*p)+dp[j]*(1-p);
        }
    }
    int m=(1+n)>>1;
    double ans=0;
    for(int i=m;i<=n;i++)
        ans+=dp[i];
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
s = str(input())

if len(s) == 2:
    if s[0] == s[1]:
        print(1,2)
    else:
        print(-1,-1)
#3文字以上
else:
    for i in range(len(s)-2):
        if s[i] == s[i+1]:
            print(i+1,i+2)
            break
        elif s[i+1] == s[i+2]:
            print(i+2,i+3)
            break
        elif s[i] == s[i+2]:
            print(i+1,i+3)
            break
        if i==len(s)-3:
            print(-1,-1)
            

Measured memory_bytes: 3188
N, K = map(int,input().split())
sweet = [list(map(int,input().split())) for s in range(K*2)]
tmp = []
for index,s in enumerate(sweet):
	if index % 2 != 0:
		if len(s) >= 2:
			for ss in s:
				tmp.append(ss)
		else:
			tmp.append(*s)
print(N - len(set(tmp)))

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

int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	bool flag = false;
	if(a % 3 == 0) flag = true;
	if(b % 3 == 0) flag = true;
	if((a + b) % 3 == 0) flag = true;
	if(flag) puts("Possible");
	else puts("Impossible");
	return 0;
}

Measured memory_bytes: 256
#ifdef __APPLE__

	#include <cassert>
	#include <iostream>
	#include <iomanip>
	#include <ctime>
	#include <cstdio>
	#include <vector>
	#include <algorithm>
	#include <utility>
	#include <queue>
	#include <stack>
	#include <string>
	#include <cstring>
	#include <sstream>
	#include <map>
	#include <set>
	#include <unordered_map>
	#include <unordered_set>

#else

	#include <bits/stdc++.h>

#endif  

using namespace std;

vector< vector <int> > graph(200001);
int visited[200001];
bool answer;
long long N;

void DFSvisit(int u, int depth)
{
	if ( answer == true)
		return;
	int len, i;
	visited[u] = 1;
	len = graph[u].size();
	if ( u == N )
		answer = true;
	if ( depth == 2 )
		return;
	for (i = 0; i < len; i++)
	{
		if ( visited[graph[u][i]] == 0 )
		{
			DFSvisit(graph[u][i], depth+1);
		}
	}
}

int main()
{
	long long M, i, v1, v2;
	scanf("%lld %lld",&N,&M);
	memset(visited,0,200001);
	answer = false;
	for ( i = 0; i < M; i++ )
	{
		scanf("%lld %lld",&v1,&v2);
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	DFSvisit(1, 0);
	if ( answer == false )
		printf("IMPOSSIBLE");
	else
		printf("POSSIBLE");
	return 0;
}







Measured memory_bytes: 12784
n, x = map(int, input().split())
l = list(map(int, input().split()))

def gcd(x, y):
    while (y != 0):
        x, y = y, x%y

    return x

ans = abs(l[0] - x)

for d in l[1:]:
    ans = gcd(ans, abs(d - x))

print(ans)


Measured memory_bytes: 15020
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		double L = sc.nextDouble();
		double areaLength = L / 3;

		String printStr = String.format("%.12f", areaLength * areaLength * areaLength);
		System.out.println(printStr);
	}
}


Measured memory_bytes: 24660
from bisect import bisect_left, bisect_right


N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
ans = 0
for b in B:
    a_upperbound = bisect_left(A, b)
    c_lowerbound = bisect_right(C, b)
    ans += a_upperbound * (N - c_lowerbound)
print(ans)


Measured memory_bytes: 29556
#include<iostream>
using namespace std;
int main(){
    int N, A[210];
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }

    int counter = 0;
    bool frag = false;
    while(1){
        for (int i = 0; i < N; i++){
            if (A[i] % 2 == 1) frag = true;
        }
        if (frag == true) break;
        for (int i = 0; i < N; i++) A[i] /= 2;
        counter += 1;
    }
    cout << counter << endl;
    return 0;
}

Measured memory_bytes: 256
// Date: 2020-03-17

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)x.size())
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

struct node {
    int w, s, v, id;
    bool operator < (const node& r) const { return w + s < r.w + r.s; }
} a[N];

int n;
LL dp[1010][20010];

int main() {
    FIO;
    cin >> n;
    rep(i, 1, n) cin >> a[i].w >> a[i].s >> a[i].v, a[i].id = i;
    sort(a+1, a+1+n);
    LL ans = 0;
    rep(i, 1, n) rep(j, 0, a[i].s + a[i].w) {
        dp[i][j] = dp[i-1][j];
        if(j >= a[i].w && j-a[i].w <= a[i].s) chkmax(dp[i][j], dp[i-1][j-a[i].w] + a[i].v);
    }
    rep(i, 0, 20000) chkmax(ans, dp[n][i]);
    cout << ans;

    return 0;
}

Measured memory_bytes: 157824
# C - Vacation
def main():
    N, *ABC = map(int, open(0).read().split())
    prev = ABC[:3]
    for a, b, c in zip(*[iter(ABC[3:])] * 3):
        cur = [0] * 3
        cur[0] = max(prev[1:]) + a
        cur[1] = max(prev[0], prev[2]) + b
        cur[2] = max(prev[:2]) + c
        prev = cur
    print(max(prev))


if __name__ == "__main__":
    main()


Measured memory_bytes: 35636
#include "bits/stdc++.h"
using namespace std;

int main() {
    int N, Y;
    cin >> N >> Y;
    int res10000 = -1, res5000 = -1, res1000 = -1;

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

            if (i * 10000 + j * 5000 + (N - i - j) * 1000 == Y && (N - i - j) >= 0){
                res10000 = i;
                res5000 = j;
                res1000 = N - i - j;
                break;
            }
        }
    }
    cout << res10000 << ' ' << res5000 << ' ' << res1000 << endl;
}

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

using namespace std;

int main()
{
    int n;
     cin>>n;
    vector<int> arr;
    vector<int> arr1;
    for(int i=0; i<n; i++)
    {
        int m;
        cin>>m;
        arr.push_back(m);
        arr1.push_back(m);
    }
    sort(arr1.begin(),arr1.end());
    int temp=0;
    int temp1=0;
    for(int i=0; i<arr.size(); i++)
    {
        if(arr[i]!=arr1[i])
        {
            temp++;
        }

    }
    if(temp==0)
    {
       cout<<"YES"<<endl;
    }
    else
    {
        /*int tempo;
        tempo=arr[arr.size()-1];
        arr[arr.size()-1]=arr[0];
        arr[0]=tempo;*/
        for(int i=0; i<arr.size(); i++)
    {
        if(arr[i]!=arr1[i])
        {
            temp1++;
        }

    }
    if(temp1==2)
    {
       cout<<"YES"<<endl;
    }
    else
         cout<<"NO"<<endl;

    }

        return 0;
}

Measured memory_bytes: 256