akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
#include <iterator>
using namespace std;
int main(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    while(k > 0){
        if(a < b && b < c)
            break;
        while(b <= a && k > 0){
            b = b*2;
            k--;
        }
        while(c <= b && k > 0){
            c = c*2;
            k--;
        }
    }
    if(a < b && b < c)
        cout << "Yes";
    else
        cout << "No";

}


Measured memory_bytes: 3592
/*
Author: CNYALI_LK
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>int dcmp(T a,T b){return a>b;}
template<int *a>int cmp_a(int x,int y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	inline void read (signed &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}

	inline void read (long long &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	inline void read (char &x) {
		x=gc();
	}
	inline void read(char *x){
		while((*x=gc())=='\n' || *x==' '||*x=='\r');
		while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
	}
	template<typename A,typename ...B>
	inline void read(A &x,B &...y){
		read(x);read(y...);
	}
	// print a signed integer
	inline void write (signed x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}

	inline void write (long long x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	inline void write (char x) {
		putc(x);
	}
	inline void write(const char *x){
		while(*x){putc(*x);++x;}
	}
	inline void write(char *x){
		while(*x){putc(*x);++x;}
	}
	template<typename A,typename ...B>
	inline void write(A x,B ...y){
		write(x);write(y...);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
int main(){
#ifdef cnyali_lk
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	int a,b;
	read(a,b);
	write(a<=0?(0<=b?"Zero\n":(a-b&1?"Positive\n":"Negative\n")):"Positive\n");
	return 0;
}



Measured memory_bytes: 2304
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;
typedef tree<
        pair<int, int>, // change type
        null_type,
        less<pair<int, int> >, // change type
        rb_tree_tag,
        tree_order_statistics_node_update>
        ordered_set;

typedef long long ll;
#define rep(i, start, end) for(int i = start; i < end; ++i)
#define per(i, start, end) for(int i = (int)start-1; i >= end; --i)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(d, v) memset(d, v, sizeof(d))
#define pii pair<int, int>
const double PI = 3.14159265358979323846;
const double eps = (1e-8);


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
////    freopen("facebook.txt", "w", stdout);
//#endif
    int n, a, b;
    cin >> n >> a >> b;
    int freq[3] = {0};
    rep(i,0,n)
    {
        int x;
        cin >> x;
        if (x <= a)
            freq[0]++;
        else if (x > a && x <= b)
            freq[1]++;
        else if (x > b)
            freq[2]++;
    }
    cout << min(freq[0], min(freq[1], freq[2]));
    return 0;
}

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

int main(){
    int a[101][101]={{}};
    int r,c;
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>a[i][j];
            a[i][c]+=a[i][j];
            a[r][j]+=a[i][j];
            a[r][c]+=a[i][j];
        }
    }
    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            if(j!=0) cout<<' ';
            cout<<a[i][j];
        }
        cout<<'\n';
    }
}


Measured memory_bytes: 3128
import sys
N = list(input())

if N.count("9") == len(N):
    print(len(N)*9)
    sys.exit(0)
if N.count("9") == len(N)-1:
    for n in range(len(N)):
        if N[n] != "9":
            if n == 0:
                i = int(N[n])
                print(i+((len(N)-1)*9))
                sys.exit(0)
            else:
                print(8+((len(N)-1)*9))
                sys.exit(0)

for n in range(len(N)-1):
    i = int(N[n])
    if i != 9:
        cnt1 = len(N[:n])
        cnt2 = len(N[n+1:])
        print((cnt1*9)+(i-1)+(cnt2*9))
        sys.exit(0)

Measured memory_bytes: 9188
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var K = Sarray()[0];
            var Calc = 13;

            var dp = new long[10,Calc][];//左端が1、桁数、num
            for (var i = 0; i < 10; ++i)
                for (var j = 0; j < Calc; ++j)
                    dp[i, j] = new long[10];
            for (var l = 0; l <= 9; ++l)
            {
                dp[l, 1][l] = 1;
                for (var i = 2; i < Calc; ++i)
                {
                    dp[l, i][0] = dp[l, i - 1][0] + dp[l, i - 1][1];
                    for (var j = 1; j < 9; ++j)
                        dp[l, i][j] = dp[l, i - 1][j - 1] + dp[l, i - 1][j] + dp[l, i - 1][j + 1];
                    dp[l, i][9] = dp[l, i - 1][8] + dp[l, i - 1][9];
                }
            }
            var rui = 0L;
            var keta = 0L;
            var ban = 0L;
            var top = 0L;
            var flg = false;
            var ans = new List<long>();
            for (var k = 1; k < Calc; ++k)
            {
                for (var l = 1; l <= 9; ++l)
                {
                    ban = rui;
                    rui = rui + dp[l, k].Sum();
                    if (K <= rui)
                    {
                        ban = K - ban;
                        keta = k;
                        top = l;
                        flg = true;
                        ans.Add(top);
                    }
                    if (flg) break;
                }
                if (flg) break;
            }
            //ketaの小さい方からban番目
            //WriteLine($"{keta}桁で頭が{top}の{ban}番目");
            while (1 != keta)
            {
                var next = ban;
                rui = 0L;
                --keta;
                for (var l = Max(0, top - 1); l <= Min(9, top + 1); ++l)
                {
                    ban = rui;
                    rui = rui + dp[l, keta].Sum();
                    if (next <= rui)
                    {
                        ban = next - ban;
                        top = l;
                        ans.Add(top);
                        break;
                    }
                }
                //WriteLine($"{keta}桁で頭が{top}の{ban}番目");
            }
            WriteLine(string.Join("", ans));
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
    using namespace std;
   int a[100010],b[100010],vis[100010],h[1000010];
    int main()
    {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++)
    {

        if(h[a[i]]==h[b[i]]){vis[a[i]]=-1,vis[b[i]]=-1;}
        if(h[a[i]]>h[b[i]]){vis[b[i]]=-1;if(vis[a[i]]!=-1)vis[a[i]]=1;}
         if (h[b[i]]>h[a[i]]){if(vis[b[i]]!=-1)vis[b[i]]=1;vis[a[i]]=-1;}
    }
    int c=0;
    for(int i=1;i<=n;i++)
        if(vis[i]==1||vis[i]==0)c++;
     cout<<c<<endl;
     return 0;
    }




Measured memory_bytes: 5160
#include<bits/stdc++.h>
int MOD = 1000000007;
using namespace std;
//g++ -std=c++14
//setprecision(10)
int main(){
	int n;
	cin >> n;
	int a;
	int va = 0;
	for(int i = 0; i < n; i++){
		cin >> a;
		if(a % 2 == 1)
			va++;
	}
	cout << (va % 2 == 1 ? "NO" : "YES") << endl;
	
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int H, W, i, j;
    
    while (1) {
        scanf("%d %d", &W, &H);
        if (H == 0 && W == 0)   break;
        
        for (i = 0; W > i; i++)
        {
            for (j = 0; H > j; j++) {
                if (i == 0 || i == (W - 1) || j == 0 || j == (H - 1))
                {
                    putchar('#');
                } else {
                    putchar('.');
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}

Measured memory_bytes: 576
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1048576")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef tuple <int, int, int> t3;

int IT_MAX = 1 << 12;
const ll MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 1234567890123456789ll;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)

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

int main() {
	int N, i;
	ll ans = 1;
	ll t;
	scanf("%d", &N);
	while (N--) {
		scanf("%lld", &t);
		ans = lcm(ans, t);
	}
	return !printf("%lld\n", ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{ 
  int A,B,C,X;
  int ans=0;
  cin>>A>>B>>C>>X;
  for(int i=0;i<=A;i++){
     for(int j=0;j<=B;j++){
        for(int k=0;k<=C;k++){
           if(X==(i*500+j*100+k*50)){
           ans++;
           } 
        }
     }
  }
  cout<<ans;
  system("pause");
  return 0;
}


Measured memory_bytes: 504
#include <iostream>
#include <cmath>

using namespace std;

int N, T, A;

float calc(int x)
{
	return fabs(T - 0.006 * x - A);
}

int main()
{
  	cin >> N;
  	cin >> T;
  	cin >> A;
  	  
  	int elev, spot = 1;
  	float diff, min;
  
  	cin >> elev;
 	diff = calc(elev);
  	min = diff;
  
  	for (int i = 1; i < N; i++){
    	cin >> elev;
 		diff = calc(elev);
      	if (min > diff){
        	min = diff;
          	spot = i + 1;
        }
    }
  
  	cout << spot << endl;
  	
  	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/**
******************* Author:Bisnu sarkar ****************************
**/
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
#define fRead(x)       freopen(x,"r",stdin)
#define fWrite(x)      freopen (x,"w",stdout)
#define ull            unsigned long long
#define ll             long long
#define pii            pair<int,int>
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second
#define endl           '\n';
#define sz(s)          (int)s.size()
#define all(s)         s.begin(),s.end()
#define IO             ios_base::sync_with_stdio(false),cin.tie(NULL);  
#define what_is(x)     cerr << #x << " is " << x << endl;
///*....Debugger....*///
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << ", ";
  err(++it, args...);
}
///*....Input....*///
template <typename T> inline void Int(T &n) {
  n = 0; int f = 1; register int ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
  n = n * f;
}
 
template <typename T, typename TT> inline void Int(T &n, TT &m) { Int(n); Int(m); }
template <typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) { Int(n, m); Int(l);}
double ind(){double x; scanf("%lf",&x);return x;}

///*....Bitmask....*///
int set_1(int n,int pos){return n = (n | (1<<pos));}
int reset_0(int n,int pos){return n= n & ~(1<<pos);}
bool check_bit(int n,int pos){return n = n & (1<<pos);}

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

///*....Constraints....*///
const int N = (int) 1e6 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);
const double eps=1e-9;

int a[N];
int main()
{
    int t=1,te=0;
    //Int(t);
    while(t--){
      int n;
      Int(n);

      for(int i=1;i<=n;++i){
        Int(a[i]);
      }
      sort(a+1,a+n+1);

      ll res=0ll;
      res+=a[n];
      for(int i=n-1,j=n-1;j>1;--i){
        if(j > 2)res+=a[i]*2ll;
        else{
          res+=(ll)a[i];
        }
        j-=2;
      }
      printf("%lld\n", res);

        //printf("Case %d: ",++te);
    }
    return 0;
}






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

using namespace std;

int main(){
    double a, b, x, h, Ha, v, tg, rez, y;
    cin>>a>>b>>x;
    v=a*a*b;
    Ha=x/(a*a);
    h=b-Ha;
    if(v<=2.0*x) rez=90-atan2(a/2,h)*180/acos(-1);
    else{
        y=(2.0*x)/(b*a);
        rez=atan2(b,y)*180/acos(-1);
    }
    cout<<fixed<<setprecision(10)<<rez;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const long long MOD = 1000000007;

template<typename T>
class BinaryIndexedTree{
    public:
        BinaryIndexedTree(int sz){
            data.assign(++sz, 0);
        }

        T sum(int k){
            T ret = 0;
            for(++k; k > 0; k -= k & -k) ret += data[k];
            return (ret);
        }

        void add(int k, T x){
            for(++k; k < data.size(); k += k & -k) data[k] += x;
        }

    private:
        vector<T> data;
};

ll N, Q;
ll ball[500010], last[500010];
ll L[500010], R[500010];
vector<pll> query;
map<pll, ll> mp;

signed main(){
    cin >> N >> Q;
    ll c, l, r;
    REP(i, N){
        cin >> ball[i];
        ball[i]--;
        last[i] = -1;
    }
    REP(i, Q){
        cin >> l >> r;
        l--; r--;
        L[i] = l; R[i] = r;
        query.push_back(pll(l, r));
    }
    sort(ALL(query), [](pll x, pll y) -> bool{return ((x.second == y.second) ? (x.first < y.first) : (x.second < y.second));});
    BinaryIndexedTree<ll> bit(N);
    l = r = 0;
    for(auto q : query){
        l = q.first;
        while(r <= q.second){
            if(last[ball[r]] >= 0) bit.add(last[ball[r]], -1);
            last[ball[r]] = r;
            bit.add(last[ball[r]], 1);
            r++;
        }
        if(l == 0) mp[pll(q.first, q.second)] = bit.sum(r - 1);
        else mp[pll(q.first, q.second)] = bit.sum(r - 1) - bit.sum(l - 1);
    }
    REP(i, Q){
        PRINT(mp[pll(L[i], R[i])]);
    }
    return 0;
}

Measured memory_bytes: 62448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/* clang-format off */
#define MOD 1000000007
#define INF 1000000000
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(a) (a).begin(), (a).end()
#define __DEBUG__
#ifdef __DEBUG__
#define CH_P(a) cout <<"check_point("<<#a<<")" << "\n";
#define DEBUG(x) cout<<#x<<":"<<x<<"\n"
#define DEBUGS(v) cout << #v << ":";for(auto x:v){cout<<x<<" ";}cout<<"\n"
#endif
#ifndef __DEBUG__
#define CH_P(a) 
#define DEBUG(x) 
#define DEBUGS(v) 
#endif
/* clang-format on */

int main() {
  ll n, k, ans = 0;
  cin >> n >> k;
  vector<ll> a(n);
  ll t;
  REP(i, n) {
    cin >> a[i];
    if (a[i] == 1) t = i;
  }
  ll y;
  if (t != 0) ans += ceil((double)(t) / (k - 1));
  y = ans * (k-1) - t;


  if (t != n - 1) ans += max(0ll,(ll)ceil((double)(n - t -1-y) / (k - 1)));
  cout << ans << endl;
  return 0;
}


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

typedef long long int lli;
typedef long long ll;
typedef long double ld;

int main(){
    int t=1;
    //cin>>t;
    while(t--){
        int n;
        cin>>n;
        ll MOD=1e9+7;
        map<int,int> a;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            a[x]++;
        }
        if(n%2==0){
            for(auto j: a){
                if(j.first%2==0 || j.second!=2){
                    cout<<0;
                    return 0;
                }
            }
            ll ans=1;
            for (int i=0; i<n/2; i++) {
                ans *= 2;
                ans %= MOD;
            }
            cout<<ans;
        }
        else{
            for(auto j: a){
                if(j.first==0 && j.second!=1){
                    cout<<0;
                    return 0;
                }
                else{
                    if(j.first%2!=0 && j.second!=2){
                    cout<<0;
                    return 0;
                }
                }
            }
            ll ans=1;
            for (int i=0; i<n/2; i++) {
                ans *= 2;
                ans %= MOD;
            }
            cout<<ans;
        }
    }
}

Measured memory_bytes: 3200
N, A, B = map(int, input().split())

if(B-A<0):
    print("0")
    exit()
if(A==B):
    print("1")
    exit()

if(N==1):
    if(A==B):
        print("1")
        exit()
    else:
        print("0")
        exit()

if(N==2):
    print("1")
    exit()

print(B*(N-2)-A*(N-2)+1)





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

int main(){
	int a1,a2,b1,b2;
	cin >> a1 >> a2 >> b1 >> b2;
	if(a1 + a2 > b1 + b2) {
		cout << "Left";
	}
	else {
		if(a1 + a2 < b1 + b2) cout << "Right";
		else cout << "Balanced";
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int a,b;
    char c;
    scanf("%d %c %d",&a,&c,&b);
    if(c=='+'){
        printf("%d\n",a+b);
    }
    if(c=='-'){
        printf("%d\n",a-b);
    }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ll x;
    cin >> x;
    ll gohyaku=x/500;
    ll go=(x-gohyaku*500)/5;
    cout << gohyaku*1000+go*5<<endl;
    return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use std::cmp;
use std::collections::*;

pub struct Scanner {
    line: Vec<String>,
    idx: usize,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        return Scanner {
            line: vec![],
            idx: 0,
        };
    }
    fn next<T: std::str::FromStr>(&mut self) -> T {
        if self.idx == self.line.len() {
            let mut buffer = String::new();
            std::io::stdin().read_line(&mut buffer).ok();
            let a: Vec<&str> = buffer.trim().split(' ').collect();
            self.line = a.iter().map(|&s| String::from(s)).collect();
            self.idx = 0;
        }
        let ret: T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
        self.idx += 1;
        ret
    }
    fn next_string(&mut self) -> Vec<char> {
        let s: String = self.next();
        return s.chars().collect::<Vec<char>>();
    }
    fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        let mut v: Vec<T> = Vec::with_capacity(n);
        for _i in 0..n {
            v.push(self.next());
        }
        v
    }
}

fn main() {
    let mut scan = Scanner::new();
    let n: usize = scan.next();
    let a: Vec<i32> = scan.next_vec(n);

    let mut cnt: HashMap<i32, i64> = HashMap::with_capacity(n);
    let mut ans: i64 = 0;

    for i in 0..n {
        if let Some(c) = cnt.get(&(a[i] - i as i32)) {
            ans += c;
        }
        match cnt.get_mut(&(-a[i] - i as i32)) {
            Some(x) => {
                *x += 1;
            }
            None => {
                cnt.insert(-a[i] - i as i32, 1);
            }
        }
    }
    println!("{}", ans);
}


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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string st;
	cin >> st;
	for(ll i=0; i<8; i++){
		ll cur = 0;
		if(i&(1<<0))
			cur = (st[0]-'0') - (st[1]-'0');
		else
			cur = (st[0]-'0') + (st[1]-'0');
		if(i&(1<<1))
			cur -= (st[2]-'0');
		else
			cur += (st[2]-'0');
		if(i&(1<<2))
			cur -= (st[3]-'0');
		else
			cur += (st[3]-'0');
		if(cur == 7){
			cout << st[0];
			if(i&(1<<0))
				cout << "-";
			else
				cout << "+";
			cout << st[1];
			if(i&(1<<1))
				cout << "-";
			else
				cout << "+";
			cout << st[2];
			if(i&(1<<2))
				cout << "-";
			else
				cout << "+";
			cout << st[3] << "=7";
			return 0;
		}
	}
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int N;
    cin >> N;
    int a;
    map<int,int> mp;
    
    for(int i=0;i<N;i++){
        cin >> a;
        mp[a - 1]++;
        mp[a    ]++;
        mp[a + 1]++;
    }
    int ans = 0;
    for(auto x : mp){
        int p = x.second;
        if(p>ans)ans = p;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4736
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
int main()
{
  int w,h,n;
  for(;cin>>w>>h>>n;)
    {
      int x[n],y[n];
      for(int i=0;i<n;i++)
	{
	  cin>>x[i]>>y[i];
	  x[i]--;
	  y[i]--;
	}
      int nowx=x[0],nowy=y[0];
      int cnt=0;
      for(int i=0;i<n;i++)
	{
	  int diffx=x[i]-nowx;
	  int diffy=y[i]-nowy;
	  int tmpcnt=0;
	  if(diffx>0)
	      while(diffx>0&&diffy>0)
		{
		  diffx--;
		  diffy--;
		  tmpcnt++;
		}
	  else if(diffx<0)
	      while(diffx<0&&diffy<0)
		{
		  diffx++;
		  diffy++;
		  tmpcnt++;
		}
	  tmpcnt+= max(diffx,-diffx);
	  tmpcnt+= max(diffy,-diffy);
	  nowx=x[i];
	  nowy=y[i];
	  cnt+=tmpcnt;
	}
      cout<<cnt<<endl;
    }
}

Measured memory_bytes: 1164
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n,t,ma=0,ans=0,mi=20000000000000;
    vector<long long> a(111111);
    cin >> n >> t;
    for (int i=0; i<n; i++)
        cin >> a[i];
    mi=a[0];
    for (int i=1; i<n; i++) {
        mi=min(mi,a[i]);
        if (a[i]-mi>ma) {
            ma=a[i]-mi;
            ans=1;
        } else if (a[i]-mi==ma) ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1152
import java.util.Scanner;


public class Main {
	public static void main(String args[]){
		Scanner scanner = new Scanner(System.in);
		int input= scanner.nextInt();
		int input2 = scanner.nextInt();
		String enz = input>input2 ? " > " : input==input2 ? " == " : " < ";
		System.out.println("a"+enz+"b");
		scanner.close();
	}
}

Measured memory_bytes: 17308
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N,H, n,m , M, K,a;

vector<ll> v;
int main(){
	cin >> N >> M;
	ll v, w;
	vector<ll> dp(1e5 + 1, 1e12);
	dp[0] = 0;
	for(int i = 0; i < N; ++i){
		cin >> w >> v;
		for(int j = 1e5; j >= 0; --j){
			if(j - v >= 0) dp[j] = min(dp[j], dp[j - v] + w);
		}
	}
	ll ans =0;
	for(int i = 0; i < 1e5 + 1 ; ++i){
		if(dp[i] <= M) ans = max((ll)i, ans);
	}
	cout << ans << endl;
}



Measured memory_bytes: 1152
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = Integer.parseInt(sc.next());

    int a[] = new int[N];
    boolean flag = true;

    int ind = 0;
    for (int i = 2; i < 1852; i++) {
      flag = false;
      int p = 30 * i + 1;
      for (int j = 2; j < p; j++) {
        if (p % j == 0) {
          flag = true;
          break;
        }
      }
      if (!flag) {
        a[ind] = p;
        ind++;
        if (ind >= N) {
          break;
        }
      }
    }

    for (int i = 0; i < N; i++) {
      System.out.print(a[i] + " ");
    }
  }
}

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


int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	/*
	for(int& x : a){
		cin >> x;
	}

	IS THE SAME AS

	for(x = 0; x < a.size(); x++){
		cin >> x;
	}
	*/
	// int& = 
	for(int& x : a){
		cin >> x;
	}
	sort(a.begin(), a.end());
	long long answer = 0;
	for(int i = 0; i < n-k; ++i){
		answer += a[i];
	}
	cout << answer << endl;
	return 0;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main{
	public static void main(String args []){
    	Scanner sc=new Scanner(System.in);
      	char a[]=sc.next().toCharArray();
      	char b[]=sc.next().toCharArray();
      	int count=0;
      	for(int i=0;i<a.length;i++){
        	if(a[i]==b[i]){
            	count++;
            }
        }
      	System.out.println(count);
      
    }
}

Measured memory_bytes: 20948
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,b;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>b;
        a.at(b-1)=i+1;
    }
    for(int i=0;i<n-1;i++){
        cout<<a.at(i)<<" ";
    }
    cout<<a.at(n-1)<<"\n";
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=105;
const int maxq=1005;

struct edge{int to,cap,cost,rev;};

int n,m,k;
int d[maxn];
int a[maxn];
int p1[maxn];
int p2[maxn];
bool inq[maxn];
vector<edge>G[maxn];

void add_edge(int u,int v,int c,int w) {
	G[u].pb(edge{v,c,w,int(G[v].size())});
	G[v].pb(edge{u,0,-w,int(G[u].size()-1)});
}

int mcmf(int s,int t) {
	int flow=0 , cost=0;
	while (1) {
		memset(d,0x3f,sizeof(d));
		d[s]=0; a[s]=max(0,k-flow);
		int qh=0,qt=0,q[maxq];
		q[qt++]=s; inq[s]=1;
		while (qh<qt) {
			int u=q[qh++];
			inq[u]=0;
			for (int i=0;i<G[u].size();i++) {
				edge e=G[u][i];
				if (d[e.to]>d[u]+e.cost && e.cap) {
					d[e.to]=d[u]+e.cost;
					a[e.to]=min(a[u],e.cap);
					p1[e.to]=u;
					p2[e.to]=i;
					if (!inq[e.to]) {
						q[qt++]=e.to;
						inq[e.to]=1;
					}
				}
			}
		}
		if (d[t]==INF || !a[t]) break;
		flow+=a[t];
		cost+=a[t]*d[t];
		for (int u=t;u!=s;u=p1[u]) {
			edge e=G[p1[u]][p2[u]];
			G[p1[u]][p2[u]].cap-=a[t];
			G[e.to][e.rev].cap+=a[t];
		}
	}
	if (flow<k) return -1;
	else return cost;
}

int main() {
	cin>>n>>m>>k;
	for (int i=0;i<m;i++) {
		int u,v,c,w; cin>>u>>v>>c>>w;
		add_edge(u,v,c,w);
	}
	cout<<mcmf(0,n-1)<<'\n';
}



Measured memory_bytes: 3200
n = gets.to_i
arr = gets.chomp.split.map(&:to_i)
count, checked = 0, []
0.upto(n - 1){|i|
    next if checked[i]
    current, step, h = i, 0, {}
    until checked[current]
        checked[current] = true
        h[current] = step
        step += 1
        current = (current + arr[current]) % n
    end
    count += step - h[current] if h[current]
}
puts count



Measured memory_bytes: 22572
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

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


	ll N = 0, K = 0;
	char c;
	while ((c = getchar_unlocked()) >= '0') N = N * 10 + c - '0';
	while ((c = getchar_unlocked()) >= '0') K = K * 10 + c - '0';

	int A[200001];
	int D2[200001];
	rep1(i, N) A[i] = getint();

	int d = 0;
	int p = 1;
	while (A[p] > 0) {
		D2[d] = p;
		int tugi = A[p];
		A[p] = -d++;
		p = tugi;
	}
	if (K > -A[p]) {
		ll k = K + A[p];
		k %= d + A[p];
		K = -A[p] + k;
	}
	printf("%d", D2[K]);

	Would you please return 0;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    int x[n];
    rep(i, n) cin >> x[i];

    int ans = 1e9;
    for (int i = 0; i <= n - k; i++) {
        int l = x[i];
        int r = x[i + k - 1];
        ans = min(ans, r - l + min(abs(r), abs(l)));
    }

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


Measured memory_bytes: 640
#include<iostream>

using namespace std;

int main()
{

    int a = 0, b, c, d , e, k;
    int x[6];

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

    cin >> k;

    for(int i = 0; i < 5; i++)
    {
        for(int j = i + 1; j < 5; j++)
        {
            if(x[j] - x[i] <= k)
            {
                a = 1;
            }
            else
            {
                a = 0;
                break;
            }
        }
        if(!a)
          break;
    }

    if(a)
    {
        cout << "Yay!"<< endl;
    }

    else
       cout << ":(" << endl;


    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
    public static void Main()
    {
        while (true)
        {
            int n = int.Parse(Console.ReadLine());
            if (n == 0) break;
            int[] s = (from elem in Console.ReadLine().Split(' ') select int.Parse(elem)).ToArray();
            double m = s.Average();
            Console.WriteLine(Math.Sqrt((from elem in s select (elem - m) * (elem - m)).Average()));
        }
    }
}


Measured memory_bytes: 16336
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

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

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;++i)
    {
        cin >> a[i];
    }
    vector<int> heads;
    heads.push_back(-1); //guard
    for(int i=n-1;i>=0;--i)
    {
        auto iter = upper_bound(heads.begin(), heads.end(), a[i]);
        if(iter == heads.end())
        {
            heads.push_back(a[i]);
        }
        else
        {
            *(iter) = a[i];
        }
    }
    cout << (heads.size() - 1) << endl;;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int x;
  int count=0;
  cin >>x;
  while (x>=500){
    x=x-500;
    count=count+1000;
  }
  while (x>=5){
    x=x-5;
    count=count+5;
  }
  cout << count <<endl;
}

Measured memory_bytes: 256
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
    ll a, b;
    cin>>a>>b;
    cout<<a*b<<endl;
}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3860
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
 
void merge(vector<int> &A, int left, int mid, int right){
    int n1 = mid - left;
    int n2 = right - mid;
    vector<int> L, R;
    L.resize(n1 + 1);
    R.resize(n2 + 1);
    for(int i = 0; i < n1; i++){
        L[i] = A[left + i];
    }
    for(int i = 0; i < n2; i++){
        R[i] = A[mid + i];
    }
    L[n1] = numeric_limits<int>::max();
    R[n2] = numeric_limits<int>::max();
    int i = 0;
    int j = 0;
    for(int k = left; k < right; k++){
        if(L[i] <= R[j]){
            A[k] = L[i];
            i = i + 1;
        }else{
            A[k] = R[j];
            j = j + 1;
        }
    }
}
 
void mergeSort(vector<int> &A, int left, int right, int &count)
{
    if(left+1 >= right){
        return;
    }
    int mid = (left + right)/2;
    mergeSort(A, left, mid, count);
    mergeSort(A, mid, right, count);
    merge(A, left, mid, right);
    count += right - left;
}
 
int main()
{
    int n;
    int count = 0;
    cin >> n;
    vector<int> S;
    S.resize(n);
    for(int i = 0; i < n; i++){
        cin >> S[i];
    }
    mergeSort(S, 0, n, count);
    for(int i = 0; i < n-1; i++){
        cout << S[i] << ' ';
    }
    cout << S[n-1] << endl << count << endl;
    return 0;
}

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

int main(){
    ll n;
    ll mxw;
    cin>>n>>mxw;
    vector<ll>w(n);
    vector<ll>v(n);
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    vector<ll>a(500000,1000000000000000);
    a[0]=0;
    for(int i=0;i<n;i++){
        for(ll j=a.size()-1;j>= v[i];j--){
            a[j]=min(a[j],a[j-v[i]]+w[i]);
        }
    }
    ll ans=-1;
    for(ll i=1;i<a.size();i++){
        if(a[i]<=mxw){ans=i;}
    }
    cout<<ans;

    return 0;

}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char a[15];
	for(int i=1;i<=12;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=4;i++)
	{
		cout<<a[i];
	}
	cout<<" ";
	for(int i=5;i<=12;i++)
	{
		cout<<a[i];
	}
	cout<<endl; 
	return 0; 
} 

Measured memory_bytes: 256
from collections import defaultdict

n = int(input())
dict1 = defaultdict(int)

for i in range(n):
    s = str(input())
    dict1[s] += 1

dict1 = sorted(dict1.items(), key=lambda x:x[1], reverse=True)
max = dict1[0][1]
ans = []
for i in range(len(dict1)):
    if dict1[i][1] == max:
        ans.append(dict1[i][0])
    else:
        break

ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 43484
import numpy as np
n=int(input())
l=list(map(int,input().split()))


arr=np.array(l)
arr2=np.append(np.hstack((0,arr)),0)
differ=np.sum(np.abs(np.diff(arr2)))
dif=np.diff(arr2)
for i in range(1,n+1):
    difference=abs(dif[i]+dif[i-1])-abs(dif[i])-abs(dif[i-1])
    print(differ+difference)

   


Measured memory_bytes: 22960
n,k=map(int,input().split())
s=list(map(int,input().split()))
total=0
for i in range(k):
  total+=s[i]
max=total
for i in range(k,n):
  total+=s[i]-s[i-k]
  if total>max:
    max=total
print((max+k)/2)

Measured memory_bytes: 25060
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 1000010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000003;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

ll fac[MAX_N], inv[MAX_N], fiv[MAX_N]; //fiv:inv(fac(i))

ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}

ll invf(ll a) {
	return mod_pow(a, mod - 2);
}

void C_init(int n) {
	fac[0] = fac[1] = 1; inv[1] = 1;
	fiv[0] = fiv[1] = 1;
	rep(i, 2, n + 1) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fiv[i] = fiv[i - 1] * inv[i] % mod;
	}
}

ll C(int a, int b) { //assume a >= b
	if(a < b || a < 0 || b < 0) return 0;
	return fac[a] * fiv[b] % mod * fiv[a - b] % mod;
}


int Q;
int X, D, N;

void solve() {
	C_init(mod - 1);
	cin >> Q;
	while(Q--) {
		cin >> X >> D >> N;
		if(D == 0) cout << mod_pow(X, N) << "\n";
		else {
			if(X == 0) cout << mod_pow(D, N) * fac[N - 1] % mod << "\n";
			else {
				ll n = X * inv[D] % mod;
				if(n + N - 1 < mod) {
					cout << mod_pow(D, N) * fac[n + N - 1] % mod * fiv[n - 1] % mod << "\n";
				}
				else cout << 0 << "\n";
			}
		}
	}
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 24320
import java.io.*;
import java.util.*;

class Main{
	public static void main(String[] args){
		solve();
	}
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] d = new int[n];
		for(int i=0;i<n;i++){
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		int count = 1;
		for(int i=0;i<n-1;i++){
			if(d[i]!=d[i+1]){
				count++;
			}
		}
		System.out.println(count);
	}
}


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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if(a+b+c != 17){
        cout << "NO";
        return 0;
    }else{
        if(a == 5 || a ==7){
            if(b == 5|| b == 7){
                if(c == 5|| c == 7){
                    cout << "YES";
                    return 0;
                }
            }
        }
    }
    cout << "NO";
}

Measured memory_bytes: 256
import java.util.*;

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

        ArrayList<int[]> list = new ArrayList<int[]>();
        for (int i=0;i<W;i++) {
            p[i] = sc.nextInt();
            int[] add = {p[i], 0};
            list.add(add);
        }
        for (int i=0;i<H;i++) {
            q[i] = sc.nextInt();
            int[] add = {q[i], 1};
            list.add(add);
        }
        Collections.sort(list, (o1, o2)->Integer.compare(o1[0], o2[0]));

        int p_used = 0;
        int q_used = 0;
        long ans = 0L;
        for (int i=0;i<W+H;i++) {
            int val = list.get(i)[0];
            int flag = list.get(i)[1];
            if (flag==0) {
                ans += (long)val*(H+1-q_used);
                p_used++;
            } else { // flag==1
                ans += (long)val*(W+1-p_used);
                q_used++;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 95992
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    int N;
    string A,B,C;
    cin>>N>>A>>B>>C;
    int count=0;
    for(int i=0;i<N;i++){
        if(A.at(i)==B.at(i)&&B.at(i)==C.at(i)){continue;}
        else if(A.at(i)==B.at(i)||B.at(i)==C.at(i)||C.at(i)==A.at(i)){count++;}
        else{count+=2;}}
        
    cout<<count<<endl;
    return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n,l;
	cin >> n >> l;
	vector<int> a(n);
	vector<int> ans;
	int id=-1;
	for(int i=0;i<n;i++)
		cin >> a[i];
	for(int i=1;i<n;i++)
		if(a[i]+a[i-1]>=l)
			id=i;
	if(id==-1)
	{
		cout <<"Impossible"<< endl;
		return 0;
	}

	
	cout <<"Possible"<< endl;
	for(int i=1;i<id;i++)
		ans.push_back(i);
	for(int i=n-1;i>=id;i--)
		ans.push_back(i);
	

	for(int i=0;i<n-1;i++)
		cout << ans[i] << endl;


}

Measured memory_bytes: 1784
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,COUNT) for(int i=0;i<(int)(COUNT);i++)
typedef long long ll;
#define MOD 1000000007
int N;
double dp[301][301][301];
double solve(int i,int j,int k){
  if(i < 0 || j < 0 || k < 0)
    return 0.0;
  if(dp[i][j][k] != -1)
    return dp[i][j][k];
  return dp[i][j][k] = (N+(double)i*solve(i-1,j,k)+(double)j*solve(i+1,j-1,k)+(double)k*solve(i,j+1,k-1))/(double)(i+j+k);
 
  
}

int main()
{
  ll a[4],g,sum;
  cin >> N;
  REP(i,4)a[i] = 0;
  REP(i,N){
    cin >> g;
    a[g]++;
    sum += g;
  } 
  REP(i,301)REP(j,301)REP(k,301)dp[i][j][k] = -1;
  dp[0][0][0] = 0;
  printf("%.16lf\n",solve(a[1],a[2],a[3]));
  return 0;
}



Measured memory_bytes: 213376
# sys.stdin.readline()
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
t = list(map(int, input().split()))
vd = 0
ans = 0
for i in range(N-1):
    if t[i+1]-t[i] < T:
        vd += t[i+1]-t[i]
    else:
        ans += vd+T
        vd = 0
print(ans+T+vd)

Measured memory_bytes: 25748
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#include<stdio.h>
#include<deque>
#include<iomanip>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef pair<int, int> P;

int main() {
 
	string S, T;
	cin >> S >> T;
 
	if (T.size() > S.size()) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
 
 
	vector<int> candidate_pos;
	for (int i = 0; i < S.size() - T.size() + 1; i++) { //先頭から何文字目でヒットするか
		bool match = true;
		for (int n = 0; n < T.size(); n++) { // Tの文字列を総当たりでチェック
			if (T[n] != S[i + n] && S[i + n] != '?') {
				match = false;
				break;
			}
		}
		if (match) candidate_pos.push_back(i);
	}
 
	if (candidate_pos.size() == 0) {
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
 
	vector<string> output_array;
	for (int n = 0; n < candidate_pos.size(); n++) {
		string out_put = S;
		for (int i = 0; i < T.size(); i++) {
			out_put[candidate_pos[n] + i] = T[i];
		}
		for (int i = 0; i < out_put.size(); i++) {
			if (out_put[i] == '?') out_put[i] = 'a';
		}
		output_array.push_back(out_put);
	}
	sort(output_array.begin(), output_array.end());
 
	cout << output_array[0] << endl;
 
	return 0;
 
}

Measured memory_bytes: 256