akhauriyash/Code-Regression huggingface dataset:
use std::io::BufRead;

fn main() {
    let stdin = std::io::stdin();
    let (n, m): (usize, usize) = stdin.lock().gets().split(' ').values();
    let mut edges = vec![Vec::new(); n];
    let mut sv = vec![0; m];
    for (i, line) in stdin.lock().lines().take(m).map(|x| x.unwrap()).enumerate() {
        let (u, v, s): (usize, usize, i64) = line.split(' ').values();
        edges[u - 1].push((v - 1, s));
        edges[v - 1].push((u - 1, s));
        sv[i] = s;
    }

    let mut unique = None;
    let mut visited = vec![None; n];
    let mut stack = vec![(0, 0, true)];
    let (mut posmin, mut negmin) = (std::i64::MAX, std::i64::MAX);
    while let Some((n, acc, positive)) = stack.pop() {
        if let Some((acc2, positive2)) = visited[n] {
            if positive == positive2 {
                if acc != acc2 {
                    println!("0");
                    return;
                }
            } else {
                let sol = if positive { acc2 - acc } else { acc - acc2 };
                if sol % 2 != 0 {
                    println!("0");
                    return;
                }
                let sol = sol / 2;
                if let Some(x) = unique {
                    if sol != x {
                        println!("0");
                        return;
                    }
                } else {
                    unique = Some(sol);
                }
            }
            continue;
        }
        visited[n] = Some((acc, positive));
        if positive {
            posmin = std::cmp::min(posmin, acc);
        } else {
            negmin = std::cmp::min(negmin, acc);
        }
        for &(n2, s) in &edges[n] {
            stack.push((n2, s - acc, !positive));
        }
    }
    if let Some(sol) = unique {
        if posmin + sol > 0 && negmin - sol > 0 {
            println!("1");
        } else {
            println!("0");
        }
    } else {
        println!("{}", std::cmp::max(posmin + negmin - 1, 0));
    }
}

trait Gets { fn gets(&mut self) -> String; }
impl<T: std::io::BufRead> Gets for T {
    fn gets(&mut self) -> String { self.lines().next().unwrap().unwrap() } }

trait Values<T> { fn values(&mut self) -> T; }
impl<'a, I, T1, T2> Values<(T1, T2)> for I
    where I: Iterator<Item=&'a str>,
          T1: std::str::FromStr, T1::Err: std::fmt::Debug,
          T2: std::str::FromStr, T2::Err: std::fmt::Debug {
    fn values(&mut self) -> (T1, T2) {
        (self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap())
    }
}
impl<'a, I, T1, T2, T3> Values<(T1, T2, T3)> for I
    where I: Iterator<Item=&'a str>,
          T1: std::str::FromStr, T1::Err: std::fmt::Debug,
          T2: std::str::FromStr, T2::Err: std::fmt::Debug,
          T3: std::str::FromStr, T3::Err: std::fmt::Debug {
    fn values(&mut self) -> (T1, T2, T3) {
        (self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap(),
         self.next().unwrap().parse().unwrap())
    }
}


Measured memory_bytes: 26876
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;

namespace A
{
    partial class Program
    {
        string s;
        public IEnumerable<string> Solve()
        {
            s = Str;

            for (int i = 0; i < s.Length - 1; i++)
            {
                if (s[i] == s[i + 1])
                {
                    yield return "Bad";
                    yield break;
                }

            }


            yield return "Good";
        }
    }

    class StartingPoint
    {
        static void Main(string[] args)
        {
            if (args?.Any() == true)
            {
                var assembly = Assembly.GetExecutingAssembly();
                var resourceName = "AtCoder.Resources.In.txt";
                var stream = assembly.GetManifestResourceStream(resourceName);
                var streamReader = new StreamReader(stream, Encoding.UTF8);
                var str = streamReader.ReadToEnd();
                var textReader = new StringReader(str);
                Console.SetIn(textReader);
            }

            try
            {
                foreach (var s in new Program().Solve())
                {
                    Console.WriteLine(s);
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
                if (args?.Any() != true)
                    throw e;
            }

            if (args?.Any() == true)
                Console.ReadLine();
        }
    }

    partial class Program
    {
        long[] Nums(long count) => Enumerable.Range(0, (int)count).Select(_ => Num).ToArray();
        long Num => long.Parse(Str);
        double NumD => (double)Num;

        StringBuilder sb = new StringBuilder();

        string Str => GetStr();
        string GetStr()
        {
            sb.Clear();

            int r = 0;
            bool? b = null;
            do
            {
                r = Console.Read();
                b = IsBreak(r);
            } while (b == true);

            if (b == null)
                throw new Exception("input error: unexpected end of stream");

            do
            {
                sb.Append((char)r);
                r = Console.Read();
                b = IsBreak(r);
            } while (b == false);

            return sb.ToString();
        }

        bool? IsBreak(int c)
        {
            switch (c)
            {
                case -1:
                    return null;
                case (int)' ':
                case (int)'\n':
                case (int)'\r':
                    return true;
                default:
                    return false;
            }
        }
    }
}

Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const long double PI = 3.14159265358979323846;
#pragma GCC optimize ("-O3")

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long ans = -1e18;
    if ((a <= 0 and b >= 0) or (c <= 0 and d >= 0))
        ans = 0;
    ans = max({ans, a*c, a*d, b*c, b*d});
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3612
n = gets.to_i
cities = []
n.times { cities << gets.split.map(&:to_i) }
def distance(x1, y1, x2, y2)
  Math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
end

array = []
cities.combination(2).each do |c|
  array << distance(c[0][0], c[0][1], c[1][0], c[1][1])
end

sum = array.inject(:+)
ans = sum / array.size * (n - 1)
puts ans


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
const int inf = 1012345678;

int main(){
  int N; cin >> N;
  vector<int> V(N);
  for(int i=0;i<N;i++){
    cin >> V[i];
  }
  vector<int> C(N);
  for(int i=0;i<N;++i){
    cin >> C[i];
  }
  
  int ans = 0;
  for(int i=0;i<N;i++){
    if(V[i]>C[i]){
      ans += V[i]-C[i];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

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

    int ans=0;
    for(int i=0;i<=999;i++){
        bool ok=false;
        string k=to_string(i);
        if(i<10){
            int cnt0=0;
            bool ok0=false;
            rep(j,n){
                if(ok0){
                    if(s[j]-'0'==i) ok=true;
                }
                else{
                    if(s[j]-'0'==0){
                        cnt0++;
                        if(cnt0==2) ok0=true;
                    }
                }
            }
        }
        else if(i<100){
            bool ok0=false;
            int l=0;
            rep(j,n){
                if(ok0){
                    if(s[j]==k[l]) l++; 
                }
                else{
                    if(s[j]-'0'==0) ok0=true;
                }
            }
            if(l==2) ok=true;
        }
        else{
            int l=0;
            rep(j,n){
                if(s[j]==k[l]) l++;
            }
            if(l==3) ok=true;
        }
        if(ok){
            //cout<<i<<endl;
            ans++;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int N;
    int a[10000];
    cin >> N;
    for(int i = 0; i < N; ++i) cin >> a[i];
    int cnt = 0;
    for(int i = 0; i < N; ++i){
        while(true){
            if(a[i] % 2 == 0){
                cnt++;
                a[i] /= 2;
            }
            else{
                break;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}
 

Measured memory_bytes: 256
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    N = int(input())
    ans = 0
    for i in range(10**9):
        if i * i <= N:
            ans = max(ans, i * i)
        else:
            break
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define MAX (ll)(1e3 + 7)
#define INF (ll)(1e18)
#define MOD (ll)(1e9 + 7)

using namespace std;
using ll = long long;
using cd = complex<double>;

int main () {
	int n;
	cin >> n;
	cout << (1000 * (n / 1000 + (n % 1000 > 0))) - n << "\n";
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  cout << fixed << setprecision(15);
  //int ans;
  //string ans;
  char ans = '1';

  string s; ll n; cin >> s >> n;

  rep(i, min((ll)s.size(), n)) if (s[i] != '1') {ans = s[i]; break;}

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

Measured memory_bytes: 256
import sys
N, = map(int, raw_input().split())
s  = raw_input()
for i in ["SS", "SW", "WS", "WW"]:
  r = [None] * (N+2)
  r[0:2] = list(i)
  for j in range(2, N+2):
    r[j] = "S" if bool(r[j-2]=="S") ^ bool(r[j-1]=="S") ^ bool(s[(j-1)%N]=="o") else "W"
  if r[N:N+2]==list(i):
    print "".join(r[:N])
    sys.exit(0)
print -1

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

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

int main() {
	string s;
	cin >> s;
	ll ans = 0;
	//bool is_C = false;
	//for (int i = s.length() - 1; i >= 0; i--)
	//{
	//	if (s[i] == 'A')
	//		ans += nBC;

	//	if (!is_C) {
	//		if (s[i] == 'C')
	//			is_C = true;
	//		if (s[i] == 'B')
	//			nBC = 0;
	//	}
	//	else {
	//		if (s[i] == 'B')
	//			nBC++;
	//		else
	//			nBC = 0;
	//		if (s[i] != 'C')
	//			is_C = false;
	//	}
	//}
	int nBC = 0;
	int i = s.length() - 1;
	while (i >= 0) {
		while (i - 1 >= 0 and s[i - 1] == 'B' and s[i] == 'C') {
			nBC++;
			i -= 2;
		}
		if (i >= 0 and s[i] != 'A') {
			i--;
			nBC = 0;
			continue;
		}
		while (i >= 0 and s[i] == 'A') {
			ans += nBC;
			i--;
		}
	}

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

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	long long ans = 0;
	int n;
	cin >> n;
	vector<long long> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		a[i] += ans;
		if (a[i] % b[i] != 0) {
			ans += b[i] - a[i] % b[i];
		}
	}
	cout << ans << endl;
	return 0;	
}

Measured memory_bytes: 1792
n,k=map(int,input().split())
mod=10**9+7
ans=0
l=[0]*(k+1)
 
for i in range(k,0,-1):
    l[i]=pow(k//i,n,mod)
    for j in range(2*i,k+1,i):
        l[i]-=l[j]
        l[i]%=mod
    ans+=l[i]*i
    ans%=mod
 
print(ans)

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

int main() {
  int  W, H, N;
  cin >> W >> H >> N;

  struct Ant {int id, x, y; string s;};
  vector<Ant> ant(N);
  for(int i = 0; i < N; ant[i].id = ++i) cin >> ant[i].x >> ant[i].y >> ant[i].s;

  map<int, vector<Ant*>> group;
  for(auto& i: ant) group[i.x + i.y].emplace_back(&i);
  for(auto& g: group) sort(begin(g.second), end(g.second), [](auto l, auto r) {return l->x < r->x;});

  map<int, set<int>> result;

  auto white = [](auto& a) {return ! ((a.y + a.x) & 1);};
  for(auto& g: group) {
    list<int> id[2], x[2];
    for(auto& a: g.second) {
      auto p = a->x & 1;
      if(a->s == "E") id[p].emplace_back(a->id), x[p].emplace_back(a->x);
      else {
        if(!white(*a)) p = !p;
        if(!id[p].empty()) {
          id[p].emplace_back(a->id);
          a->id = id[p].front();
          id[p].pop_front();
        }
        result[H - a->y].emplace(a->id);
      }
    }
    for(auto i: {0, 1}) while(!id[i].empty()) {
      result[W - x[i].front()].emplace(id[i].front());
      id[i].pop_front();
      x[i].pop_front();
    }
  }

  for(auto i: result) for(auto j: i.second) cout << j << endl;
}

Measured memory_bytes: 66968
#include <cassert>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

struct interval { int s,t,x; };
bool cmp(const interval &l, const interval &r) { return l.s < r.s; }
bool operator<(const interval &l, const interval &r) { return l.t > r.t; }

int main() {
    int n, q; cin >> n >> q;
    vector<interval> intvs;
    for (int i = 0; i < n; i++) {
        int s, t, x; cin >> s >> t >> x;
        intvs.push_back({s-x, t-x, x});
    }
    sort(intvs.begin(), intvs.end(), cmp);
    priority_queue<interval> pq;
    multiset<int> S;
    int i = 0;
    while (q--) {
        int d; cin >> d;
        while (i < intvs.size() && intvs[i].s <= d) pq.push(intvs[i]), S.insert(intvs[i].x), i++;
        while (!pq.empty() && pq.top().t <= d) S.erase(S.lower_bound(pq.top().x)), pq.pop();
        if (S.empty()) cout << -1 << endl;
        else cout << *S.begin() << endl;
    }
}


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


Measured memory_bytes: 128
#include <stdio.h>

int main(void) {
    int a, b;

    scanf("%d%d", &a, &b);

    if (a <= 5)
        printf("%d\n", 0);
    else if (a >= 6 && a <= 12)
        printf("%d\n", b/2);
    else 
        printf("%d\n", b);

    return 0;
}

Measured memory_bytes: 128
n = int(input())
out = [0 for x in range(n)]
inp = [int(x) for x in input().split(' ')]
if n%2==0:
    for i in range(n):
        if i % 2 == 0:
            out[int(n/2) + int(i/2)] = inp[i]
        else:
            out[int(n/2) - int((i+1)/2)] = inp[i]
else:
    k = int((n-1)/2)
    for i in range(n):
        if i % 2 == 0:
            out[k - int(i/2)] = inp[i]
        else:
            out[k+int((i+1)/2)] = inp[i]
for i in out:
    print(i, end=' ')


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

int counting(int n){
    int res=0;
    while(n%2==0){
        res++;
        n/=2;
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    int res=0;
    for(int i=0;i<n;i++){
        int num;
        scanf("%d",&num);
        if(num%2==0) res+=counting(num);
    }
    printf("%d\n",res);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[200],b[200],c[200],d,n,t[200];
int p[200][200] = {0};

int rec(int day, int prev)
{
  if(day == d)return 0;
  if(p[day][prev] != -1)return p[day][prev];

  int ans = 0;

  for(int now=0; now<n; now++){
    if(a[now] <= t[day] && b[now] >= t[day]){
      ans = max(ans,rec(day+1,now) + abs(c[now] - c[prev]));
    }
  }
  return p[day][prev] = ans;
}

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

  for(int i=0; i<d; i++)
    cin>>t[i];

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

  for(int i=0; i<200; i++){
    for(int j=0; j<200; j++){
      p[i][j] = -1;
    }
  }

  int fans = 0;

  for(int i=0; i<n; i++){
    if(a[i] <= t[0] && t[0] <= b[i]){
      fans = max(fans,rec(1,i));
    }
  }
  cout<<fans<<endl;

}

Measured memory_bytes: 1328
#include <iostream>
#include <memory.h>
#include <deque>
#include <vector>
#include <stdio.h>
using namespace std;
const int MAXN = 10000;
const int INF = 100000000;
const int redirect = 0;
int N, M;
struct  Edge{
    int v, d, c;
};

int dist[MAXN], cost[MAXN];
bool inQueue[MAXN]; 
vector<Edge> g[MAXN];
deque<int> queue;


void addEdge(int u, int v, int d, int c){
    Edge e;
    e.v = v; e.d = d, e.c = c;
    g[u].push_back(e);
    e.v = u;
    g[v].push_back(e);
}

void spfa(int s){
    memset(inQueue, 0, sizeof(bool) * N);
    int i,j;
    for(i = 0; i < N; ++i)
    {
        dist[i] = INF;
        cost[i] = INF;
    }
    queue.push_back(s);
    dist[s] = 0;
    cost[s] = 0;
    inQueue[s] = true;
    while(!queue.empty()){
        int u = queue.front();
        queue.pop_front();
        //printf("Top: %d\n",u);
        for(i = 0; i < g[u].size(); ++i){
            Edge &e = g[u][i];
            if(dist[e.v] > dist[u] + e.d || dist[e.v] == dist[u] + e.d && cost[e.v] > e.c)
            {
                dist[e.v] = dist[u] + e.d;  //即使入&#38431;了，后&#32493;也能&#20248;化全局&#20540;
                cost[e.v] = e.c;
                if(!inQueue[e.v]) {    //&#36825;里&#26816;&#26597;避免重&#22797;入&#38431;
                    if(queue.empty() || dist[e.v] < dist[queue.front()]){
                        queue.push_front(e.v);
                    }else{
                        queue.push_back(e.v);
                    }
                    inQueue[e.v] = true;
                }
            }
            //printf("%d %d %d\n", e.v, dist[e.v], cost[e.v]);
        }
        inQueue[u] =  false;
    }
}

int main(){
    int i, j;
    int u, v, d, c;
    if(redirect)
        freopen("2249-input.txt", "r", stdin);

    while(1){
        scanf("%d%d", &N, &M);
        if(N==0 && M==0) 
            break;
        for(i = 0; i < N; ++i)
            g[i].clear();

        for(i = 0; i < M; ++i){
            scanf("%d%d%d%d", &u, &v, &d, &c);
            addEdge(--u, --v, d, c);
        }
        spfa(0);
        int res = 0; 
        for(i = 0; i < N; ++i){
            //printf("%d ", cost[i]);
            res += cost[i];
        }
        //printf("\n");
        printf("%d\n", res);
    }
    return 0;
}

Measured memory_bytes: 3192
N, K = map(int, input().split())
H = [0] + [int(a) for a in input().split()]
X = [[1<<100] * (N-K+1) for _ in range(N+1)]
X[0][0] = 0
for i in range(1, N+1):
    for j in range(1, min(i+1, N-K+1)):
        X[i][j] = min([X[ii][j-1] + max(H[i] - H[ii], 0) for ii in range(i)])

print(min([x[-1] for x in X]))


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

int main() {
    int antena[5];
    int k;
    for (int i = 0; i < 5; i++) {
        cin >> antena[i];
    }
    cin >> k;
    for (int i = 0; i < 4; ++i) {
        for (int j = i + 1; j < 5; ++j) {
//            printf("%d - %d = %d, (%d)\n", antena[j], antena[i], antena[j] - antena[i], k);
            if (antena[j] - antena[i] > k) {
                cout << ":(" << endl;
                return 0;
            }
        }
    }

    cout << "Yay!" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) REP(i, 0, n)
#define REP(i, l, r) for (int i = l; i < r; ++i)
#define int long long
#ifdef DEBUG
#define dout cout
#else
std::stringstream dout;
#endif
using namespace std;
typedef pair<int, int> P;
// other libs
signed main(int argc, char* argv[]) {
	int n;
	cin >> n;
	int ans = 0;
	map<string, int> mp;
	rep(i, n) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		mp[s]++;
	}
	for (pair<string, int> it : mp) {
		ans += it.second * (it.second - 1) / 2;
	}
	cout << ans << endl;
}


Measured memory_bytes: 11136
import math
a, b, x = map(int, input().split())
v = a*a*b
if x*2 > v:
	print(math.degrees(math.atan2((2*(b-(x/(a*a)))), a)))
elif x == v:
	print(0)
else:
	print(90 - math.degrees(math.atan2(((2*x)/(a*b)), b)))


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>
#include <bitset>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

ll A, B;

int main() {

	cin >> A >> B;


	cout << A * B / GCD(A, B) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> mp;
int32_t main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n, ans = 0;
	cin >> n;
	for(int x=1; x<=n; x++) {
		int y;
		cin >> y;
		ans += mp[x-y];
		mp[x+y]++;
	}
	cout << ans;
}

Measured memory_bytes: 26220
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

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

    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 1; i <= b; ++i)
    {
        if(((i * a)%b)  == c){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define INF 2001
#define NIL -1
#define WHITE 0
#define BLACK 1

main(){
	int n, i, j, u, cost=0, mincost;
	int **G, *tmp;
	int *flag;
	int *d, *pi;

	scanf("%d", &n);
	flag = (int*)malloc(sizeof(int) * n);
	d = (int *)malloc(sizeof(int)*n);
	pi = (int *)malloc(sizeof(int)*n);
	G = (int**)malloc(sizeof(int*) * n);
	tmp = (int*)malloc(sizeof(int) * n * n);
	for (i = 0; i < n; i++){
		G[i] = tmp + i * n;
	}

	for (i = 0; i < n; i++){
		flag[i] = WHITE;
		d[i]=INF;
		pi[i]=NIL;
		for (j = 0; j < n; j++){
			scanf("%d", &G[i][j]);
		}
	}

	// [0]を開始点
	u=0;
	d[u]=0;

	while(1){
	  mincost = INF;
	  for(i=0; i<n; i++){
	    if(flag[i]!=BLACK && d[i]<mincost){
	      mincost = d[i];
	      u=i;
	    }
	  }
	  if(mincost == INF) break;
	  flag[u] = BLACK;
	  cost += mincost;

	  for(i=0; i<n; i++){
	    if(G[u][i]!=-1 && flag[i]!=BLACK && G[u][i]<d[i]){
	      d[i]=G[u][i];
	      pi[i] = u;
	    }
	  }  
	}

	printf("%d\n", cost);

	free(tmp);
	free(G);
	free(flag);

	return 0;
}

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

namespace template
{
    class Program
    {
        static void Main(string[] args)
        {
            var imp = Console.ReadLine().Split(' ');

            int N = int.Parse(imp[0]);
            int K = int.Parse(imp[1]);
            int a = 0;

            a = (N % K == 0) ? 0:1;
            Console.WriteLine(a);


           






           // System.Threading.Thread.Sleep(1000);    //for debug

        }
    }
}

Measured memory_bytes: 11092
#include<iostream>
using namespace std;
long long power[32];
int main() {
	int s, t;
	power[0] = 1;
	for (int i = 1; i < 31; i++) { power[i] = power[i - 1] * 2; }
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> t;
		int cnt = 0;
		long long v = s;
		while (t > v) {
			for (int i = 30; i >= 0; i--) {
				if (t - v < power[i]) { continue; }
				if ((v%power[i]) == 0) {
					cnt++;
					v += power[i];
					break;
				}
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

int main() {
	ll n;
	cin >> n;
	vector<ll> a(n);
	vector<bool> table(n, false);
	table[n - 1] = true;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	ll ans = 0;
	ll temp;
	ll count;
	sort(a.begin(), a.end());
	for (int i = n - 2; i >= 0; i--) {
		temp = a[i];
		count = 1;
		//cout << "temp=" << temp << endl;
		if (temp * 2 >= a[i+1]) {
			//cout << "ue" << endl;
			if (table[i + 1]) {
				ans++;
				table[i] = true;
				//cout << "ok" << endl;
			}
		}
		else {
			//cout << "sita" << endl;
			while (temp * 2 < a[i+1] && i-count>=0) {
				temp += a[i - count];
				//cout <<"i-count"<<(i-count)<< " while_temp=" << temp << endl;
				if (temp*2 >= a[i+1]) {
					if (table[i + 1]) {
						//cout << "ok" << endl;
						ans++;
						table[i] = true;
					}
					break;
				}count++;
			}
		}//cout <<"ans="<< ans << endl;
	}cout << ans+1 << endl;
	return 0;
}

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

int main() {
	int n, a,b;
	int upper=1000000000;
	int lower=0;
	scanf("%d", &n);
	for(int i=0;i<n;i++){
	    scanf("%d",&a);
	    upper=min(upper,a);
	    lower=max(lower,a);
	}
	cout<<lower-upper;
	return 0;
}


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

int main(){
    int ans = 100000;
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        ans += ans*0.05;
        if(ans%1000!=0)
            ans = ans-ans%1000 + 1000;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3080
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>
#include <numeric>
#include <set>
#include <iomanip>
#define FOR(i, a, n) for (int i = (a); i < (n); i++)
#define REP(i, n) for(int i = 0; i < (n); i++)
using namespace std;

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

	string S;
	long long K;

	cin >> S >> K;

	REP(i, S.length())
	{
		if (i + 1 == K)
		{
			cout << S[i] << endl;
			break;
		}
		if (S[i] != '1')
		{
			cout << S[i] << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main  {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double odd = 0;

        for (int i = 1; i <= n; i++) {

            if (i % 2 != 0) {
                odd++;
            }

        }

        System.out.printf("%.10f\n",  (odd / n));


    }

}


Measured memory_bytes: 22356
package main

import (
	"fmt"
)

func main () {
	var k,x int
	fmt.Scan(&k)
	fmt.Scan(&x)
	for i := x+1-k; i < x+k; i++ {
		fmt.Print(i)
		if i != x+k-1 {
			fmt.Print(" ")
		} else {
			fmt.Println()
		}
	}
}

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

int main() {
    int n;cin>>n;
    ll ans=1;
    int mod=1e9+7;
    for (int i=2;i<=n;i++)
        ans=ans*i%mod;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
string S;
  cin >>S;
  if(S.at(0)==S.at(2)) {
cout <<"Yes" << endl;
  }
else {
cout << "No" << endl;
}
}


Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    String S = sc.next();
    if (S.substring(0, N/2).equals(S.substring(N/2, N))) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

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

int n;

int main(){
	cin>>n;
	vi a(3);
	for(int i=0;i<n;i++){
		int A;
		cin>>A;
		if(A%2==1) a[0]++;
		else if(A%4==0) a[2]++;
		else a[1]++;
	}
	if(a[2]>=a[0]||(a[2]+1==a[0]&&!a[1])) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#include <numeric>
#include <stdio.h>
#include <map>
#include <iomanip>
#include <sstream>
//#include <boost/math/common_factor_rt.hpp>
#include<fstream>
#define EPS (1e-7)
using namespace std;
#define ll long long



class Employee {
public:
	int id;
	int parent;
	vector<int> children;
	int salary;

	Employee() {
		
	}

	Employee(int num, int nparent) {
		id = num;
		parent = nparent;
		salary = -1;
	}



};



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





pair<int, int> count_nonzero_cluster(vector<int>& vs) {

	int number = 0;
	int prev = 0;
	int vmax = -1;
	pair<int, int> re = make_pair(number, vmax);
	for (auto& v:vs)
	{
		if (prev <= 0 && v > 0) {
			re.first += 1;
		}
		if (re.second < v)re.second = v;
		prev = v;
	}


	return re;
}

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


	int ans;
	if (N == K) {
		ans = 1;
	}
	else {
		ans = ceil((N - 1) / (double)(K - 1));
	}

	cout << ans << endl;
	return 0;


	int temp;
	for (auto i = 0; i < N; i++)
	{
		cin >> temp;
	}



}

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

using LL = long long;

#define ALL(a) begin((a)), end((a))
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define RFOR(i, a, b) for (int(i) = (a); (i) > (b); (i)--)
#define debug(x) cout << #x << " : " << x << '\n'

const int INF = 1e9;

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

  LL ans = 0;
  int N, M;
  cin >> N >> M;
  vector<LL> A(N);
  FOR(i, 0, N) { cin >> A[i]; }
  vector<pair<LL, int>> ope(M);
  FOR(i, 0, M) { cin >> ope[i].second >> ope[i].first; }

  sort(A.begin(), A.end());
  sort(ope.rbegin(), ope.rend());

  int temp = 0;
  FOR(i, 0, N) {
    if (A[i] < ope[temp].first) {
      A[i] = ope[temp].first;
      ope[temp].second--;

      if (ope[temp].second == 0) {
        temp++;
      }
    }

    ans += A[i];
  }

  // FOR(i, 0, M) { cout << ope[i].second << ' ' << ope[i].first << '\n'; }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 2688
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <typeinfo>
#define PI 3.14159265359
#define INF 99999999;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(n) rep(i, n)
#define EPS 1e-10
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

double distanceAB(double xa, double ya, double xb, double yb);

/*
class Target
{
public:
	vector <string> draw(int n)
	{

	}
};
*/


int cnt[1000001];

int main()
{
	int n, q;
	priority_queue<P> que;
	
	que.push(P(0, -1));
	fill(cnt, cnt+1000001, 0);
	cin >> n >> q;
	
	REP(q)
	{
		int a, v;
		cin >> a >> v;
		cnt[a] += v;
		que.push(P(cnt[a], -a));
		while (true)
		{
			P res = que.top();
			if (res.first == cnt[-res.second])
			{
				cout << -res.second << " " << res.first << endl;
				break;
			}
			que.pop();
		}
	}
	
	return 0;
}



double distanceAB(double xa, double ya, double xb, double yb)
{
	return sqrt((xb-xa)*(xb-xa) + (yb-ya)*(yb-ya));
}

Measured memory_bytes: 6008
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int n, big = 0, x = 0;
	char c;
	cin >> n;
	for (int i = 0;i < n;i ++) {
		cin >> c;
		if (c == 'I') x ++;
		else x --;
		big = max(big, x);
	}
	cout << big;
}

Measured memory_bytes: 256
import numpy as np
from numba import njit, int64

n = int(input())


@njit(int64(int64))
def f(n):
    cnt = np.zeros(n + 1, np.int16)
    for i in range(1, n + 1):
        cnt[i::i] += 1

    return (cnt * np.arange(n + 1)).sum()


ans = f(n)
print(ans)


Measured memory_bytes: 302308
#include <stdio.h>
#include <vector>
#include <list>
#include <array>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <stdexcept>


using std::string;
using std::vector;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// util
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

std::vector<std::string> split(const std::string& input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// user func
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void printList(const vector<int>& list) {
    // print
    for(int i = 0; i < list.size(); i++){
        printf("%d", list[i]);
        if(i != list.size() -1){
            printf(" ");
        }
    }
    printf("\n");
}



//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// logic
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

bool find(const vector<int>& list, int index, int target, int current) {
    if(list.size() <= index) return false;
    if (current + list[index] == target){
        return true;
    }
    if (find(list, index + 1, target, current + list[index])){
        return true;
    }
    if(find(list, index + 1, target, current)){
        return true;
    }
    return false;
}

void solve() {
    int n;
    scanf("%d", &n);
    vector<int> list(n);
    for(int i = 0; i < n; i++){
        int v;
        scanf("%d", &v);
        list[i] = v;
    }

    int q;
    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
        int v;
        scanf("%d", &v);
        if (find(list, 0, v, 0)) {
            printf("yes\n");
        } else {
            printf("no\n");
        }

    }



}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) REP(i, 0, n)
#define REP(i, l, r) for (int i = l; i < r; i++)
using namespace std;
typedef pair<int, int> P;
struct edge {
	int to, cost;
};
class dijkstra {
  private:
	int V;
	int d[100002];
	priority_queue<P, vector<P>, greater<>> que;

  public:
    dijkstra(int v, int s, vector<edge> G[]) {
        V = v;
        update(s, G);
    }

    void update(int s, vector<edge> G[]) {
        fill(d, d + V + 1, 100000000000ll);
        d[s] = 0;
        que.push(make_pair(0, s));
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (d[v] < p.first)
                continue;
            rep(i, G[v].size()) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(make_pair(d[e.to], e.to));
                }
            }
        }
    }

	int find(int e) {
		return d[e];
	}
};

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

int lcm(int a, int b) {
	return a * b / gcd(a, 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;
}

class Union_Find {
  private:
	vector<int> t, s;

  public:
	Union_Find(int max_length) {
		rep(i, max_length + 1) {
			t.push_back(i);
			s.push_back(1);
		}
	}

	void Union(int x, int y) {
		if (same(x, y))
			return;
		int tx = Find(x), ty = Find(y);
		if (s[tx] < s[ty]) {
			s[ty] += s[tx];
			t[tx] = ty;
		}
		else if (s[tx] > s[ty]) {
			s[tx] += s[ty];
			t[ty] = tx;
		}
		else if (tx > ty) {
			t[tx] = ty;
			s[ty] += s[tx];
		}
		else {
			t[ty] = tx;
			s[tx] += s[ty];
		}
	}

	int Find(int n) {
		if (t[n] == n)
			return n;
		else
			return t[n] = Find(t[n]);
	}

	bool same(int x, int y) {
		return Find(x) == Find(y);
	}

	int get_Size(int a) {
		return s[a];
	}
};

vector<int> primeFactorization(int n) {
	vector<int> re;
	int cnt = 2;
	while (n != 1) {
		if (n % cnt != 0) {
			cnt++;
			continue;
		}
		n /= cnt;
		re.push_back(cnt);
	}
	return re;
}

signed main() {
    int n,d[100000];
    cin>>n;
    rep(i,n)cin>>d[i];
    sort(d,d+n);
    cout<<d[n/2]-d[n/2-1]<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define MOD 1000000007
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	vector<int> h(n);
	vector<int> dp(n,INT_MAX);
	for (int i = 0; i < n; ++i)
	{
		cin>>h[i];
	}
	dp[0]=0;
	for(int i=1;i<n;++i){
		for(int j=1;j<=k && i>=j;++j){
			dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
		}
	}
	cout<<dp[n-1];
	// cerr<< '\n' << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n" ;
	return 0;
}

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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

int main() {
    int n,sum = 0;
    cin >> n;
    bitset<4000010> dp[2];
    dp[0].reset();
    dp[1].reset().set(0);
    for (int i = 0;i < n;++i) {
        int a;
        cin >> a;
        sum += a;
        dp[i&1] = dp[(i&1)^1];
        dp[i&1] |= (dp[(i&1)^1]<<a);
    }
    for (int i = (sum+1)/2;i < 4000010;++i) if (dp[(n&1)^1][i]) {
        cout << i << endl;
        break;
    }
    return 0;
}

Measured memory_bytes: 2176
n,m = map(int,input().split())
As = [int(input()) for _ in range(m)]
step = [ 0 for i in range(n+1)]
INF = 1000000007

dp = [0]*(n)

for i in As:
    step[i] = -1

for i in range(n-1):
    if step[i+1] == -1 and step[i+2] == -1:
        print(0)
        exit()
    if step[i+1] != -1:
        step[i+1] +=  1
    if step[i+2] != -1:
        step[i+2] +=  1

step[0] = 1
if step[1] != -1:
    step[1] = 1

for i in range(2,n+1):
    if step[i] == -1 or step[i] == 0:
        continue
    else:
        a = 0
        b = 0
        if step[i-2] != -1:
            a = step[i-2]
        if step[i-1] != -1:
            b = step[i-1]
        step[i] = a + b

print(step[n]%INF)



Measured memory_bytes: 460824
#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-10;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


//ここから編集

const int MAX = 2000010;
long long fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理

ll mod2 = 998244353;
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod2;
        inv[i] = mod2 - inv[mod2%i] * (mod2 / i) % mod2;
        finv[i] = finv[i - 1] * inv[i] % mod2;
    }
}
 
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod2) % mod2;
}

ll dp[3010][3010];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  
    ll A, B, C, D;
    cin >> A >>B >> C >> D;

    dp[A][B] = 1;

    for(ll i=A; i<=C-1; i++){
        dp[i+1][B] = (dp[i][B] * B) % mod2;
        //cout << i+1 << " " << B << " " << dp[i+1][B] << endl;
    }
    for(ll i=B; i<=D-1; i++){
        dp[A][i+1] = (dp[A][i] * A) % mod2;
        //cout << A << " " << i+1 << " " << dp[A][i+1] << endl;
    }

    for(ll i=A+1; i<=C; i++){
        for(ll j=B+1; j<=D; j++){
            dp[i][j] = (dp[i][j-1] * i + dp[i-1][j] * j - ((i-1)*(j-1)*dp[i-1][j-1] % mod2))%mod2;
            //cout << i << " " << j << endl;
        }
    }
    cout << dp[C][D] << endl;

    
    return 0;
}


Measured memory_bytes: 74132
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
#define MOD (1000000007ll)

bool conccomp(int x, int y, int p, int q){
	return (p*y>x*q);
}

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

bool prm[1234];
ll cnt[1234];

int main(void){
	int n,i,j,x;
	ll ans=1ll;
	fill(prm,prm+1234,true);
	fill(cnt,cnt+1234,0ll);
	prm[1] = false;
	for(i=2; i<=1234; ++i){
		for(j=2; j<i; ++j){
			if(i%j==0){
				prm[i] = false;
				break;
			}
		}
	}
	cin >> n;
	for(i=2; i<=n; i++){
		x = i;
		j = 2;
		while(x>1){
			if(!prm[j]){
				j++;
				continue;
			}
			while(x%j==0){
				x /= j;
				cnt[j]++;
			}
			j++;
		}
	}
	for(i=2; i<=n; i++){
		mul_mod(ans,cnt[i]+1);
	}
	cout << ans << endl;
	return 0;
}


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

#define forn(i, s, f) for (int i = (s); i <= (f); ++i)
#define for1(i, s, f) for (int i = (s); i >= (f); --i)
#define pb push_back

using namespace std;

typedef long long ll;

int n, m, q;

ll h[2010][2010], s[2010][2010], v[2010][2010];

char a[2010][2010];

#define int long long

main()
{
    cin >> n >> m >> q;
    forn (i, 1, n)
        forn (j, 1, m)
        {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] == '1');
            v[i][j] = v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1] + (a[i][j] == '1' && a[i - 1][j] == '1');
            h[i][j] = h[i - 1][j] + h[i][j - 1] - h[i - 1][j - 1] + (a[i][j] == '1' && a[i][j - 1] == '1');
        }
    forn (i, 1, q)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int s1 = (s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2]) + s[x1 - 1][y1 - 1];
        int s2 = (v[x2][y2] - v[x2][y1 - 1] - v[x1][y2]) + v[x1][y1 - 1];
        int s3 = (h[x2][y2] - h[x2][y1] - h[x1 - 1][y2]) + h[x1 - 1][y1];
        cout << (s1 - s2 - s3) << "\n";
    }
}


Measured memory_bytes: 100352
// #includes {{{
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <cmath>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

typedef long long Int;
typedef unsigned long long uInt;
#ifdef __MINGW32__
typedef double rn;
#else
typedef long double rn;
#endif

typedef pair<int,int> pii;

/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}

Int A,B,C;

int main(){
	cin>>A>>B>>C;
	if(A%2==0 or B%2==0 or C%2==0){
		cout<<0<<endl;
	}else{
		cout<<min({A*B,B*C,C*A})<<endl;
	}
	return 0;
}



Measured memory_bytes: 256
import sys #入力時間短縮
input = sys.stdin.readline

W,H=map(int,input().split())
p=sorted(int(input()) for i in range(W))
q=sorted(int(input()) for i in range(H))
ans=sum(p)*(H+1)+sum(q)*(W+1)
#1マスずつmax(pi,qj)→O(N^2)
#pi,qjが大きい順に列ごと消去→O(N)
for i in range(W+H-1):
  if p[len(p)-1]>=q[len(q)-1]:
    ans-=p[len(p)-1]*len(q)
    p.pop()
    if p==[]:
      print(ans)
      exit()
  else:
    ans-=q[len(q)-1]*len(p)
    q.pop()
    if q==[]:
      print(ans)
      exit()


Measured memory_bytes: 11616