akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>

using namespace std;

int main()
{
    int n, k, q;
    int a[100010];
    int player[100010];

    cin >> n >> k >> q;

    for (int i = 1; i <= n; i++) {
        player[i] = q;
    }

    for (int i = 0; i < q; i++) {
        cin >> a[i];
        player[a[i]]--;
    }

    for (int i = 1; i <= n; i++) {
        if (k - player[i] > 0) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 1408
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<list>
#include<string>
#include<algorithm>
#include<math.h>
 
using namespace std;
 
int main(){
  int N,Y;
  cin >> N >> Y;
  vector<int> ans(3,-1);
  for(int x=0;x<N+1;x++){
    for(int y=0;y<N+1;y++){
      int z = N - x - y;
      if(z>=0 && 10000*x+5000*y+1000*z==Y){
        ans.at(0) = x;
        ans.at(1) = y;
        ans.at(2) = z;
      }
    }
  }

  cout << ans.at(0) << " " << ans.at(1) << " " << ans.at(2) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <array>
#include <climits>
#include <cassert>

using namespace std;

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

const ll MOD = 1000000000 + 7;
const ll INF = LLONG_MAX;
const ll MAX_V = ll(1e5) + 5;
const double EPS = 10e-8;
const double PI = 3.14159265359;

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

ll n,a[200005]{};

int main() {
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        a[i]+=a[i-1];
    }
    ll dmin = INF;
    for(int i=1;i<n;i++){
        dmin = min(dmin,abs(a[n]-a[i]*2));
    }
    cout << dmin << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int K, S;
  cin >> K >> S;
  int ans = 0;
  rep(x, K + 1) rep(y, K + 1)
  {
    int z = S - (x + y);
    if (0 <= z && z <= K)
      ans++;
  }
  cout << ans << endl;
  return 0;
}

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

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
// 出力は.xで！！！！

int main(){
    string l; cin >> l;
    int sl=l.length();
    mint dp[100005][2];
    dp[0][0]=1;
    rep(i,sl){
      if(l[i]=='0'){
        dp[i+1][0]=dp[i][0];
        dp[i+1][1]=dp[i][1];
      }
      else{
        dp[i+1][1]=dp[i][0]+dp[i][1];
      }
      if(l[i]=='0'){
        dp[i+1][1]+=dp[i][1]*2;
      }
      else{
        dp[i+1][0]+=dp[i][0]*2;
        dp[i+1][1]+=dp[i][1]*2;
      }
    }
    mint ans=dp[sl][0]+dp[sl][1];
    cout << ans.x << endl;
return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    string a, b, c;
    cin >> a >> b >> c;

    if ((a.back() == b.front()) && (b.back() == c.front()))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  char c; cin >> c;
  int x = 'A', y = 'Z';
  int z = c;
  if(x <= z && z <= y) cout << 'A' << "\n";
  else cout << 'a' << "\n";
  return 0;
}


Measured memory_bytes: 3632
from heapq import heappush,heappop
N, M = map(int, input().split())

X = []

for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        X.append((a,b))


X = sorted(X, key=lambda x:(x[0], x[1]), reverse=True)

# print(X)
q = []
ans = 0
for i in range(1, M + 1):
    while X and X[-1][0] <= i:
        _, b = X.pop()
        heappush(q, -b)
    if q:
        ans -= heappop(q)
        
print(ans)


Measured memory_bytes: 25324
//Solution by Zhusupov Nurlan
#include <bits/stdc++.h>

using namespace std;

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

#define endl '\n'
#define pb(x) push_back(x)
#define sqr(x) ((x) * (x))
#define F first
#define S second
#define SZ(t) ((int) t.size())
#define len(t) ((int) t.length())
#define base LL(1e9 + 7)
#define fname ""
#define sz 1000 * 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
#define mp make_pair

int n, m, v, t, u, was[sz];
VI a[sz], ansl, ansr;

void dfs(int v, int f = 0) {
  was[v] = 1;
  if (!f) ansr.pb(v);
  for (int i = 0; i < a[v].size(); i++)
    if (!was[a[v][i]]) {
      dfs(a[v][i], min(f*2, 2));
      break;
    }
  if (f > 1)ansl.pb(v);
}

int main()
{
//    freopen(fname"in", "r", stdin);
//    freopen(fname"out", "w", stdout);

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

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> v >> u;
    a[v].pb(u);
    a[u].pb(v);
  }

  dfs(1, 0);
  dfs(1, 1);

  cout << ansl.size() + ansr.size() << "\n";
  for (int i = 0; i < ansl.size(); i++)
      cout << ansl[i] << " ";
  for (int i = 0; i < ansr.size(); i++)
      cout << ansr[i] << " ";
}


Measured memory_bytes: 31864
#!/usr/bin/env python3
import sys


def solve(N: int, v: "List[int]"):
    v.sort()

    while(len(v) != 0):
        if(len(v) == 1):
            x = v.pop(0)
            print(x)
            exit()
        a = v.pop(0)
        b = v.pop(0)
        v.append((a+b)/2)
        v.sort()
    

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    v = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, v)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;
int A, B, C, D;

int main() {
  cin >> A >> B >> C >> D;
  int ma = max(A, C);
  int mi = min(B, D);
  if (ma <= mi) {
    cout << mi - ma << endl;
  } else {
    cout << 0 << 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();
    int[][] fb=new int[10][10];
    for(int a=1;a<=n;a++){
      int f=a;
      while(f>=10){
        f/=10;
      }
      fb[a%10][f]++;
    }
//    System.err.println(Arrays.deepToString(fb));
    long ans=0;
    for(int a=1;a<=n;a++){
      int f=a;
      while(f>=10){
        f/=10;
      }
      ans=ans+=fb[f][a%10];
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 21716
import java.util.*;


public class Main {
    public static void main(String[] args) {
        // 自分の得意な言語で
        // Let's チャレンジ！！

        Scanner sc = new Scanner(System.in);
        while(true){
            int hight = sc.nextInt();
            int width = sc.nextInt();
            if(hight==0 && width==0){
                break;
            }
            for(int i=0;i<hight;i++){
                String draw = "";
                for(int j=0;j<width;j++){
                    if(i%2==0 && j%2==0){
                        draw += "#";
                    } else if(i%2!=0 && j%2!=0){
                        draw += "#";
                    } else {
                        draw += ".";
                    }
                }
                System.out.println(draw);
            }
            System.out.println("");
        }
        sc.close();
    }
}


Measured memory_bytes: 55036
import java.util.Scanner

fun main(args: Array<String>) {
  val scanner = Scanner(System.`in`)
  val N = scanner.nextInt()
  val L = IntArray(N + 1)
  for (i in 1..N) {
    L[i] = scanner.nextInt()
  }
  scanner.close()
  val max = L.max()!!
  if (L.sum() <= max * 2) {
    print("No")
  } else {
    print("Yes")
  }
}

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

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    ll t,i,j,temp1,temp2,x,y,z,sum=0,o,n,m,k,d;
    cin >> n>> k;
    vector <ll> a(n);
    for(i=0;i<n;i++){
        cin >> a[i];
    }
    vector <int> path;
    unordered_set <int> s;
     j = 1;
    for(i=0;i<=k;i++){
        if(s.find(j)==s.end()){
            path.push_back(j);
            s.insert(j);
            j = a[j-1];
        }
        else break;
    }
    for(i=0;i<path.size();i++){
        if(path[i]==j){
            break;
        }
        sum++;
    }
    if(sum==path.size()){
        cout << path[path.size()-1];
    }
    else{
    temp1 = k-sum;
    cout << path[sum + (temp1%(path.size()-sum))];
    }
}

Measured memory_bytes: 12264
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

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

	if (x == 1 || x == 2 * N - 1)cout << "No" << endl;
	else {
		cout << "Yes" << endl;
		vector<int> ans(2 * N);
		int cnt = 1;
		for (int i = 1; i <= 2 * N - 1; i++) {
			if (cnt == x - 1)cnt += 3;
			if (N - 1 > i || i > N + 1) {
				ans[i] = cnt;
				cnt++;

			}
			
		}
		
		ans[N] = x;
		ans[N - 1] = x - 1;
		ans[N + 1] = x + 1;
		
		for (int i = 1; i <= 2 * N - 1; i++) {
			cout << ans[i] << endl;
			//cout << ans[i] << " ";
		}

	}

}



Measured memory_bytes: 3996
import copy
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s,t=map(int,input().split())

connection=[[] for i in range(3*n)]
for i in range(m):
  connection[l[i][0]-1].append(l[i][1]-1+n)
  connection[l[i][0]-1+n].append(l[i][1]-1+2*n)
  connection[l[i][0]-1+2*n].append(l[i][1]-1)
distance=[-1 for i in range(3*n)]
distance[s-1]=0
L=[s-1]
L2=[]
L3=[]
ct=1
while len(L2)!=3*n and len(L)!=0:
  for j in range(len(L)):
    for k in range(len(connection[L[j]])):
      if distance[connection[L[j]][k]]==-1:
        distance[connection[L[j]][k]]=ct
        L3.append(connection[L[j]][k])
    L2.append(L[j])
  L=copy.copy(L3)
  L3=[]
  ct+=1
if distance[t-1]==-1:
  print(-1)
else:
  x=distance[t-1]-distance[s-1]
  if x%3==0:
    print(x//3)
  else:
    print(-1)

Measured memory_bytes: 82532
def solve():
    N = int(input())
    A = map(int, input().split())
    count = [0] * N
    ex = [i*2 if N%2!=i%2 else 0 for i in range(N)]
    for a in A:
        count[a] += a
    
    if count == ex:
        return 2**(N//2) % (10**9+7)
    else:
        return 0
    
if __name__ == '__main__':
    print(solve())

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

int flag[100],n,k,x;
int check(int x){
	while (x){
		if (flag[x%10])return 0;
		x/=10;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&k);
	while (k--)scanf("%d",&x),flag[x]=1;
	while (!check(n))n++;
	printf("%d\n",n);
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
using namespace std;
int main (void) {
    string s;

    cin >> s;

    int ans = INT_MAX;
    for (int i = 0; i < s.length(); i++) {
        char c = s[i];
        int cnt = 0;
        string ss = s;
        while (true) {
            int len = ss.length();
            bool end = true;
            for (int j = 0; j < len; j++) {
                if (ss[j] != c) {
                    end = false;
                }
            }
            if (end) {
                break;
            }

            for (int j = 0; j < len; j++) {
                if (j == len - 1) {
                    ss.pop_back();
                } else {
                    if (ss[j + 1] == c) {
                        ss[j] = c;
                    }
                }
            }
            cnt++;
        }
        ans = min(ans, cnt);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let s = read::<String>().chars().collect::<Vec<char>>();
    if (s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]) {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::map;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  int x, y; cin >> x >> y;
  cout << (x + y / 2) << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;




int main(){

	while (true){
		int n, tmp1 = 0, tmp2 = 0, a[4], cnt = 0;
		bool j = true;
		cin >> n;
		if (n == 0)break;
		tmp1 = n;
		while (tmp1 != 6174){
			rep(i, 4){
				a[i] = tmp1 % 10;
				tmp1 /= 10;
			}
			if (a[0] == a[1] && a[1] == a[2] && a[2] == a[3]){
				j = false;
				break;
			}
			sort(a, a + 4);
			tmp1 = a[0] + a[1] * 10 + a[2] * 100 + a[3] * 1000;
			tmp2 = a[3] + a[2] * 10 + a[1] * 100 + a[0] * 1000;
			tmp1 -= tmp2;
			cnt++;
		}
		if (j)cout << cnt << endl;
		else cout << "NA" << endl;
	}

	return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)

bool judge(string s){
	if(DEBUG)cout<<"s="<<s<<endl;
	REP(i,0,s.size()/2){
		if(s.at(i)!=s.at(s.size()-1-i))return false;
	}
	return true;
}

signed main(){

	string s;
	cin>>s;
	lli n = s.size();

	if(judge(s) && judge(s.substr(0,(n-1)/2)) && judge(s.substr((n+3)/2-1))){
		cout<<"Yes"<<endl;
	}
	else cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<unistd.h>
#include <array>
#include <map> 




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}

struct File {
    int aa;
    int bb;

    File(const int& aa, const int& bb)
        : aa(aa), bb(bb) {}
};

bool operator<(const File& a, const File& b)
{
    // ファイル種別、ファイル名の順番で優先順位を付けて比較
    return std::tie(a.aa, a.bb) < std::tie(b.aa, b.bb);
}
long long gcd(long long a,long long b){
  if(b==0){
    return a;
  }
  return gcd(b,a%b);
}
long long lcm(long long a,long long b){
  long long g=gcd(a,b);
  return a/g*b;
}
long long kaijo(long long x){
  long long l=10*10*10*10*10*10*10*10*10+7;
  long long sum=1;
  for(int i=x;i>0;i--){
    sum*=i;
    if(sum>l){
      sum%=l;
    }
  }
  return sum;
}







int main(){
  long long N,K;
  cin>>N>>K;
  long long a[10*10*10*10*10*10];
  for(int i=0;i<10*10*10*10*10*10;i++){
    a[i]=0;
  }
  for(int i=0;i<N;i++){
    int x,y;
    cin>>x>>y;
    a[x]+=y;
  }
  long long sum=0;
  long long ans=0;
  for(int i=0;i<10*10*10*10*10*10;i++){
    sum+=a[i];
    if(sum>=K){
      ans=i;
      break;
    }
  }
  cout<<ans<<endl;

}



  

Measured memory_bytes: 8064
#include <iostream>
#include <vector>
#include <climits>

#define SWIM    0
#define BUGS    1
#define HOME    2

using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    ll tally[] = {0, 0, 0};       //tally[SWIM|BUGS|HOME] is the number of points attainable by performing that activity last
    ll lastTally[] = {0, 0, 0};   //lastTally holds temporary values
    cin >> tally[SWIM] >> tally[BUGS] >> tally[HOME];
    int a, b, c;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> c;
        for (int j=0; j<3;j++) {lastTally[j] = tally[j];}    //copy previous tally result
        tally[SWIM] = max(lastTally[BUGS], lastTally[HOME]) + a;
        tally[BUGS] = max(lastTally[SWIM], lastTally[HOME]) + b;
        tally[HOME] = max(lastTally[SWIM], lastTally[BUGS]) + c;
    }
    
    
    cout << max(tally[SWIM], max(tally[HOME], tally[BUGS]));

    return 0;
}

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

int main()
{
	int a,b,c;
	int a2,b2,c2;
	cin >> a >> b >> c;
	if(a > b)
	{
		b2 = b;
		a2 = a;
		a = b2;
		b = a2;
	}
	if(b > c)
	{
		b2 = b;
		c2 = c;
		c = b2;
		b = c2;
	}
	if(a > b)
	{
		b2 = b;
		a2 = a;
		a = b2;
		b = a2;
	}
	
	cout << a << " " << b << " " << c << endl;
	
	return 0;
}

Measured memory_bytes: 3084
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;
typedef long long int ll;

int main()
{
    
    int N;
    string S, T;
    cin >> N >> S >> T;

    string ans;
    for (int i = 0; i < N; i++) {
        cout << S[i];
        cout << T[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>
#include <sstream>
typedef long long ll;

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

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; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[510][510];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}
/*
ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}*/
vector<ll> v(100005);
vector<ll> vis(100005, 0); ll c = 0, check = 0;
queue<ll>que;
/*void bfs(ll a, ll src) {
	vis[a] = src;
	que.push(src);
	while (!que.empty()) {
		src = que.front();
		for (ll x = 1; x <= v[src];x++) {
			if (vis[x] == 0) {
				c++;
				vis[x] = src;
				que.push(x);
			}
		}
		que.pop();
	}
}*/
int main() {
	ll a, b;
	cin >> a >> b;
	cout << a * b << endl;
}

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

using namespace std;

#define rep(i , l , r) for(int i = (l) , ___ = (r) ; i <= ___ ; ++i)
#define per(i , r , l) for(int i = (r) , ___ = (l) ; i >= ___ ; --i)

#define DEBUG(...) fprintf(stderr , __VA_ARGS__)

template<typename T>inline int chkmin(T &x , const T &y){ return x > y ? x = y , 1 : 0; }
template<typename T>inline int chkmax(T &x , const T &y){ return x < y ? x = y , 1 : 0; }

template<typename T>inline T read(T &f)
{
	f = 0 ; int x = 1 ; char c = getchar();
	while(!isdigit(c)) x = c == '-' ? -1 : 1 , c = getchar();
	while(isdigit(c)) (f *= 10) += c & 15 , c = getchar();
	return f *= x;
}

using int64 = long long;
using uint64 = unsigned long long;

const int N = 1000 + 5;

int n , A[N][N];

#define ID(x , y) ((x - 1) * n + y)

const int M = N * N;

struct Edge
{
	int to ; Edge *next;
} E[M << 1] , *pre[M];

int S = 0;

int deg[N];

void addedge(int u , int v)
{
	static int cnt = 0;
	E[++cnt] = {v , pre[u]} , pre[u] = &E[cnt];
	++deg[v];
}

int tp[N] , vis[N] , c = 0;

int main()
{
	read(n);
	rep(i , 1 , n)
	{
		rep(j , 1 , n - 1)
		{
			read(A[i][j]);
		}
	}
	int d = 0;
	rep(i , 1 , n) tp[i] = 1;
	while(true)
	{
		++d;
		int c = 0;
		rep(i , 1 , n) vis[i] = 0;
		rep(i , 1 , n) if(!vis[i] && tp[i] <= n - 1)
		{
			int v = A[i][tp[i]];
			if(vis[v]) continue;
			if(A[v][tp[v]] != i)
			{
				continue;
			}
			vis[i] = 1 , tp[i]++;
			vis[v] = 1 , tp[v]++;
			c++;
		/*
		rep(i , 1 , n) cout << tp[i] << ' ' ;
		cout << endl;
		rep(i , 1 , n) cout << vis[i] << ' ' ;
		cout << endl;
		*/
		}
		int flag = 1;
		rep(i , 1 , n) flag &= (tp[i] > (n - 1));
		if(flag) break;
		if(c == 0)
		{
			puts("-1");
			return 0;
		}
	}
	cout << d << endl;
	return 0;
}


Measured memory_bytes: 4736
n = gets.chomp.to_i
s = gets.chomp
count =0
for i in 0..(n-1) do
    if s[i] == "A"
        if s[i+1] == "B"
            if s[i+2] == "C"
                count += 1
            end
        end
    end
end
puts count

Measured memory_bytes: 1788
O=input()
E=input()
ans=[]
for m in range(len(O)+len(E)):
    ans.append('k')
for i in range(len(O)):
    ans[2*i]=O[i]
for j in range(len(E))   :
    ans[2*j+1]=E[j]

ans=''.join(ans)
print(ans)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
int N, K;
long long mod = 1000000007;
long long m[100001];
long long pow_mod(long long a, long long b) {
    if (b == 0) return 1;
    long long k = pow_mod(a, b/2);
    k = (k*k) % mod;
    if (b % 2 == 0) return k;
    return (k*a) % mod;
}
long long count(int K) {
    if (m[K]) return m[K];
    long long res = pow_mod(K, N);
    for (int i = 2; i <= K; i++) {
        res -= count(K/i);
        res %= mod;
    }
    res += mod;
    return m[K] = res % mod;
}
int main () {
    cin >> N >> K;
    long long ans = 0;
    for (int i = 1; i <= K; i++) {
        ans += count(K/i)*i;
        ans %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3696
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (int i = m; i < n; ++i)
#define FORR(i, m, n) for (int i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,k;cin >> n >> m >> k;
    REP(i,n+1){
        REP(j,m+1){
            if(m*i+n*j-2*i*j==k){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3616
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
d = {'r':'p', 'p':'s', 's':'r'}
ans = [d[i] for i in t]
for i in range(k, n):
    if ans[i-k] == 'x':
        continue
    if ans[i-k] == ans[i]:
        ans[i] = 'x'
total = 0
for i in ans:
    if i == 'r':
        total+=r
    elif i == 'p':
        total+=p
    elif i == 's':
        total+=s
print(total)

Measured memory_bytes: 4212
#include <cstdio>
#include <cstring>
#include <cctype>

int main()
{
    char W[10],T[1000];
    int counter = 0;
    int T_length;

    scanf("%s", W);
    for(int i = 0; W[i] != '\0'; i++){
        if(isupper(W[i])) W[i] = tolower(W[i]);
    }

    while(scanf("%s", T) != EOF){
        T_length  = strlen(T);
        for(int i = 0; T[i] != '\0'; i++){
            if(isupper(T[i])) T[i] = tolower(T[i]);
        }
        if(strcmp(T, W) == 0){
            counter++;
        }
    }
    printf("%d\n", counter);

    return 0;
}

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

#define FOR(i,a,b) for(ll i=a; i<b; i++)
#define IN(a) cin>>a
#define OUT(a) cout<<a<<endl

int main(){
 int l, r, d;
 cin>>l>>r>>d;
  int ans=0;
 for(int i=l; i<=r; i++){
   if(i%d==0){
     ans++;
   }
 }
  OUT(ans);
}


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
int main(void){
    long long  n,k;cin>>n>>k;
    cout<<(n/k)*(n/k)*(n/k)+(((k+1)%2)?((n/(k/2))-(n/k))*((n/(k/2))-(n/k))*((n/(k/2))-(n/k)):0)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
	string s;
	int sum,i;
	cin >> s;
	sum = 0;
	for(i = 0; i < (int)s.size(); i++)	sum +=s[i] - '0';
	if(sum % 9 == 0)	cout << "Yes" << endl;
	else				cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3744
#include <stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int a[n][2];
    int c[n];
    for(int b=0;b<n;b++){
        scanf("%d",&a[b][0]);
        a[b][1]=b+1;
        c[a[b][0]-1]=a[b][1];
    }
    for(int d=0;d<n;d++){
        printf("%d\n",c[d]);
    }
    return 0;
}

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

using namespace std;

void solve(void)
{
	int n;
	string s;
	cin >> s;
	n = s.size();
	vector<int> os(n), es(n, 1);
	for (int i = 0; i < n; i++)
	{

		if (s[i] == 'R')
		{
			os[i + 1] += es[i];
			es[i + 1] += os[i];
			es[i] = os[i] = 0;
		}
	}
	for (int i = n-1; i >= 0; i--)
	{
		if (s[i] == 'L')
		{
			os[i-1] += es[i];
			es[i-1] += os[i];
			es[i] = os[i] = 0;
		}
	}
	for (int i = 0; i < n; i++)
	{
		//cout << es[i] << ' ' << os[i] << '\n';
		if (s[i] == 'R')
		{
			es[i + 1] += os[i];
		}
		else
		{
			es[i - 1] += os[i];
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << es[i] << ' ';
	}
	cout << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,coin,day;
    coin=0;
    day=0;
    cin>>a>>b>>c;
    
    while(1){
        if(coin>=c){
            break;
    }
    coin=a+coin;
    day=day+1;
    if(day%7==0){
        coin=coin+b;
    }
    
    }
    cout<<day<<endl;
}


Measured memory_bytes: 3116
import java.util.*;


class Main{
	public static void main(String[] args){
   	 Scanner sc = new Scanner(System.in);
   	 int[] array = new int[10000];
  	 int N = sc.nextInt();
   	 int Allice = 0;
     int Bob = 0;
     for (int i=0; i< N; ++i){
    	array[i] = sc.nextInt(); 
   	 }
     Arrays.sort(array,0,N);
     for (int i=N-1; i >= 0; i=i-2){
     Allice += array[i];
     }
     for (int i=N-2; i >= 0; i=i-2){
     Bob += array[i];
     }
     System.out.println(Allice-Bob);
     
    }
  
}

Measured memory_bytes: 22100
import java.util.*;
public class Main{
 	public static void main(String args[]){
     	Scanner sc=new Scanner(System.in);
      	String s=sc.nextLine();
      	int l=s.length();
      	int win=15-l;
      	for(int i=0;i<l;i++){
         	 if(s.charAt(i)=='o')
               win++;
        }
      if(win>=8)
        System.out.println("YES");
      else
        System.out.println("NO");
    }
}

Measured memory_bytes: 23508
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
#define BR "\n"
#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it,cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it,cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)

#define DumpArray(cont,from,to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

using namespace std;
typedef long long ll;
typedef long double ld;
ll N,M,P;
ll answer=0;
struct Edge{ll to,gain;};
vector<ll> d;
vector<bool> V;
vector<vector<Edge>> G;
int main() {
    cin >>N >> M >>P;
    G.resize(N);
    d.resize(N);
    V.resize(N,false);
    REP(i,M) {
        ll A,B,C;
        cin>>A>>B>>C;--A;--B;C-=P;
        G[A].pb({B,C});
    }
    V[0]=true;
    d[0]=0;
    ll loops=0;
    while(true) {
        if (loops==M) {
            answer=d[N-1];
        }
        if (loops>M*2) {
            if (answer!=d[N-1]) {
                cout << -1 << endl;
            }else {
                cout << max((ll)0,d[N-1]);
            }
            exit(0);
        }
        bool updated=false;
        for(int i=0;i<G.size();++i) {
            if (V[i]) {
                for(int j=0;j<G[i].size();++j) {
                    Edge& e=G[i][j];
                    if (!V[e.to] || d[e.to]<d[i]+e.gain) {
                        V[e.to]=true;
                        updated=true;
                        d[e.to]=d[i]+e.gain;
                    }
                }
            }
        }
        if (!updated)break;

        loops+=1;
    }
    cout << max((ll)0,d[N-1]);
    return 0;
}


Measured memory_bytes: 512
n=int(input())
ac_list=[input() for i in range(n)]
AC = ac_list.count('AC')
WA = ac_list.count('WA')
TLE = ac_list.count('TLE')
RE = ac_list.count('RE')
print("AC x {}".format(AC))
print("WA x {}".format(WA))
print("TLE x {}".format(TLE))
print("RE x {}".format(RE))

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

namespace q4
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = Convert.ToInt64(Console.ReadLine());
            var arr = Console.ReadLine().Split(' ').Select(x => Convert.ToInt64(x)).ToArray();
            var nums = new long[n+1];
            var total = 0L;
            for (var i = 0; i < arr.Length; i++)
            {
                var x = arr[i];
                nums[x] += 1;
            }
            for (var i = 0; i < n+1; i++)
            {
                total += (nums[i] * (nums[i] - 1)) / 2;
            }
            for (var i = 0; i < arr.Length; i++)
            {
                var x = arr[i];
                Console.WriteLine(total - nums[x] + 1);
            }
        }
    }
}


Measured memory_bytes: 39612
#include <iostream>

using namespace std;

int main()
{
  int N,tmp,cnt;
  bool j;

  cin >> N;

  tmp = N%10;
  N /= 10;
  cnt = 0;

  while ( N > 0 ) {
    int tmp2 = N % 10;
    if ( tmp2 != tmp ) {
      cnt = 0;
      tmp = tmp2;
    } else {
      ++cnt;
      if ( cnt >= 2 ) break;
    }

    N /= 10;
  }

  if ( cnt >= 2 ) cout << "Yes\n";
  else cout << "No\n";
}


Measured memory_bytes: 888
//#include "pch.h"
#include "stdio.h"
#include "stdlib.h"

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

	int nPrev;
	int nNext;

	nNext = n % 10;
	n /= 10;

	int flag = 0;
	for (int i = 3; i > 0; i--)
	{
		nPrev = nNext;
		nNext = n % 10;
		n /= 10;
		if (nNext == nPrev)
		{
			flag = 1;
			break;
		}
	}

	if (flag)
		printf("Bad");
	else
		printf("Good");

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
string to_string(const string& s) {
	return '"' + s + '"';
}
string to_string(const bool b) {
	return (b ? "true" : "false");
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(const char c) {
	string s = "'";
	s += c;
	s += "'";
	return s;
}
template<class T, class U>
string to_string(const pair<T, U>& p) {
	string s = "(";
	s += to_string(p.first);
	s += ", ";
	s += to_string(p.second);
	s += ")";
	return s;
}
template<class T>
string to_string(const T& a) {
	bool first = true;
	string s = "{";
	for (const auto& x : a) {
		if(!first){
			s += ", ";
		}
		first = false;
		s += to_string(x);
	}
	s += "}";
	return s;
}
void debug_out() {cerr << '\n';}
template<class Head, class... Tail>
void debug_out(Head head, Tail... tail) {
	cerr << ' ' << to_string(head);
	debug_out(tail...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 7e18l;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	ld W, H, x, y;
	cin >> W >> H >> x >> y;
	cout << W * H / 2 << ' ';
	if (x == W / 2 && y == H / 2) {
		cout << 1 << '\n';
	} else {
		cout << 0 << '\n';
	}
 	return 0;
}


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

int main() {
	ll x;

	cin >> x;
	int x1 = x / 500;
	int joy = 0;
	int max_joy = 0;
	for(int i = 0; i <= x1; i++) {
		joy = 1000 * i;
		ll y = x - 500 * i;
		joy = joy + (y / 5) * 5;
		max_joy = max(max_joy, joy);
	}
	cout << max_joy << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

    for(int i=0; i<H; i++){
      String s = sc.next();
      System.out.println(s);
      System.out.println(s);
    }
  }
}
    
    

Measured memory_bytes: 37256
#include <iostream>
#include <deque>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#define llint long long
#define mod 1000003
#define inf 1e18

using namespace std;
typedef pair<llint, llint> P;

llint Q;

const int FACT_MAX = 1000003;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

int main(void)
{
	cin >> Q;
	make_fact();
	
	llint x, d, n;
	for(int q = 0; q < Q; q++){
		cin >> x >> d >> n;
		
		if(d == 0){
			cout << modpow(x, n) << endl;
			continue;
		}
		if(n >= mod){
			cout << 0 << endl;
			continue;
		}
		llint l = modpow(d, mod-2) * x % mod;
		llint r = modpow(d, mod-2) * (x + (n-1)*d%mod) % mod;
		if(l > r){
			cout << 0 << endl;
			continue;
		}
		llint ans = fact[r];
		if(l > 0) ans *= fact_inv[l-1], ans %= mod;
		else ans = 0;
		ans *= modpow(d, r-l+1), ans %= mod;
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 16512
#include<iostream>
using namespace std;
int main()
{
    string s,t,ans="Yes";
    cin>>s>>t;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=t[i])
    {
        ans="No";
        break;
    }
    }
    cout<<ans;
}

Measured memory_bytes: 3596
#include <bitset>
#include <iostream>

using BitSet = std::bitset<32>;

int main(void) {
    unsigned long long x;
    std::cin >> x;

    BitSet my_bitset(x);
    const BitSet my_bitset_flip = ~my_bitset;
    const BitSet my_bitset_left = my_bitset << 1;
    const BitSet my_bitset_right = my_bitset >> 1;

    std::cout << my_bitset << std::endl;
    std::cout << my_bitset_flip << std::endl;
    std::cout << my_bitset_left << std::endl;
    std::cout << my_bitset_right << std::endl;
}


Measured memory_bytes: 3136
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#pragma GCC optimize ("O2")
#pragma GCC optimize ("tree-vectorize")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class CHAndV {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int H, W, K;
        in>>H>>W>>K;
        vc<string> G(H);
        for(auto& g : G) in>>g;
        int ans = 0;
        REP(i, 1<<H) REP(j, 1<<W){
            int cur = 0;
            REP(k, H){
                if((i>>k)&1) continue;
                REP(l, W){
                    if((j>>l)&1) continue;
                    if(G[k][l]=='#') ++cur;
                }
            }
            if(cur==K) ++ans;
        }
        out<<ans<<'\n';
    }
};


int main() {
	CHAndV solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3652
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)

















int main(){
    ll n;
    cin >> n;
    if(n == 2){
        cout << 1 << endl;
        return 0;
    }
    ll ans = 0;
    map<ll, bool> mp;
    for(ll i = 2; i <= sqrt(n); i++){
        if((n - 1) % i == 0){
            mp[i] = true;
            mp[n / i] = true;
        }
        else{
            ll m = n;
            while(m % i == 0){
                m /= i;
            }
            if(m % i == 1) ans++;
        }
    }
    cout << ans + mp.size() + 2 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const int INF (1 << 30);
const ll LLINF (1LL << 55LL);
const int MOD = 1000000007;
const int MAX = 510000;
const double pi = acos(-1);
const double eps = 1e-9;

struct UnionFind {
    vector<ll> par;
        
    UnionFind(ll n) : par(n, -1) { }
    void init(ll n) { par.assign(n, -1); }
    
    ll find(ll x) {
        if (par[x] < 0) return x;
        else return par[x] = find(par[x]);
    }
    
    bool same(ll x, ll y) {
        return find(x) == find(y);
    }
    
    bool unite(ll x, ll y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    ll size(ll x) {
        return -par[find(x)];
    }

    void print(ll x){
        rep(i,x){
            cout<<par[i]<<endl;
        }
        return ;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    rep(j,INF){
        ll n,b,k,ans=0;
        cin>>n>>b>>k;
        if(n==0&&b==0&&k==0){
            break;
        }
        bool t[100190]={};
        pair<ll,pll> s[100010];
        vll G;
        UnionFind uf(n);
        rep(i,n-1){
            ll p,q,r;
            cin>>p>>q>>r;
            p--;q--;
            s[i]=mp(r,pll(p,q));
        }
        sort(s,s+n-1);
        reverse(s,s+n-1);
        rep(i,b){
            ll d;
            cin>>d;
            d--;
            t[d]=true;
        }
        rep(i,n-1){
            ll z1=uf.find(s[i].sc.sc);
            ll z2=uf.find(s[i].sc.fi);
            if(t[z1]==true&&t[z2]==true){
                G.pb(s[i].fi);
            }
            else if(t[z1]==true||t[z2]==true){
                uf.unite(z1,z2);
                t[uf.find(z1)]=true;
            }
            else{
                uf.unite(z1,z2);
            }
        }
        sort(all(G));
        rep(i,k){
            ans+=G[i];
        }
        cout<<"Case "<<j+1<<": "<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 5692
#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
typedef long long LL;
const int N=100005;
int n,a[N];
int GCD(int x,int y) {return y?GCD(y,x%y):x;}
int work() {
	LL sum=0;int js=0,x,gcd;
	for(RI i=1;i<=n;++i) {
		sum+=a[i]-1;
		if((a[i]&1)&&a[i]!=1) ++js,x=i;
	}
	if(sum&1) return 1;
	if(js!=1) return 0;
	--a[x],gcd=a[1];
	for(RI i=2;i<=n;++i) gcd=GCD(gcd,a[i]);
	for(RI i=1;i<=n;++i) a[i]/=gcd;
	return work()^1;
}
int main()
{
	n=read();
	for(RI i=1;i<=n;++i) a[i]=read();
	if(work()) puts("First");
	else puts("Second");
	return 0;
}

Measured memory_bytes: 640
N, C, K = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

T.sort()

ans = 1
cnt = 1
t = T[0]

for i in range(1, N):
  if T[i] - t > K or cnt >= C:
    ans += 1
    cnt = 1
    t = T[i]
  else:
    cnt += 1

print(ans)

Measured memory_bytes: 80960