akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int INF=1001001001;
int N;
vint G[100000];
int K;
int C[100000];

int L[100000],R[100000];

int pa[100000];

void dfs(int v,int p){
    if(C[v]!=INF)L[v]=R[v]=C[v];
    for(auto u:G[v]){
        if(u==p)continue;
        dfs(u,v);
        chmax(L[v],L[u]-1);
        chmin(R[v],R[u]+1);
    }
}

void dfs2(int v,int p,int pl,int pr){
    chmax(L[v],pl-1);
    chmin(R[v],pr+1);


    vint max_l(G[v].size()+1,-INF),min_r(G[v].size()+1,INF);
    vint l(G[v].size()),r(G[v].size());
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i];
        if(u!=p){
            l[i]=L[u];
            r[i]=R[u];
        }
        else{
            l[i]=pl;
            r[i]=pr;
        }
        max_l[i+1]=max(max_l[i],l[i]);
        min_r[i+1]=min(min_r[i],r[i]);
    }

    int ll=-INF,rr=INF;
    for(int i=G[v].size()-1;i>=0;i--){
        int u=G[v][i];
        if(u!=p){
            dfs2(u,v,max(max_l[i],ll)-1,min(min_r[i],rr)+1);
        }
        chmax(ll,l[i]);
        chmin(rr,r[i]);
    }
}

signed main(){
    scanf("%lld",&N);
    rep(i,N-1){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        G[a].pb(b);G[b].pb(a);
    }
    scanf("%lld",&K);
    queue<int>que;
    memset(pa,-1,sizeof(pa));
    fill_n(C,N,INF);
    rep(i,K){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;
        C[a]=b;
        pa[a]=b&1;
        que.push(a);
    }

    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto u:G[v]){
            if(pa[u]!=-1){
                if(pa[u]==pa[v]){
                    puts("No");
                    return 0;
                }
                continue;
            }

            pa[u]=1-pa[v];
            que.push(u);
        }
    }
    fill_n(L,N,-INF);
    fill_n(R,N,INF);

    dfs(0,-1);
    dfs2(0,-1,-INF,INF);
    rep(i,N){
        if(L[i]>R[i]){
            puts("No");
            return 0;
        }
    }

    fill_n(C,N,INT_MAX);
    C[0]=L[0];
    que.push(0);
    while(que.size()){
        int v=que.front();
        que.pop();
        for(auto u:G[v]){
            if(C[u]!=INT_MAX)continue;
            int nc;
            if(C[v]-1>=L[u])C[u]=C[v]-1;
            else C[u]=C[v]+1;
            que.push(u);
        }
    }
    puts("Yes");

    rep(i,N)printf("%lld\n",C[i]);
    return 0;
}


Measured memory_bytes: 33792
#include <iostream>
typedef unsigned long ul;
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	unsigned int a[210];
	int n;
	cin >> n;
	REP(i, n)
	{
		cin >> a[i];
	}
	int cnt = 0;
	while (1)
	{
		REP(i, n)
		{
			if (a[i] % 2 == 0)
			{
				a[i] = a[i] / 2;
			}
			else
			{
				cout << cnt;
				return 0;
			}
		}
		cnt++;
	}
}

Measured memory_bytes: 888
import math

N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]


def check(n):
    d = n * B
    t = 0
    for h in H:
        if h <= d:
            continue
        t += (h - d + (A - B - 1)) // (A - B)
    return t <= n


lo, hi = 0, 10 ** 9

while lo < hi:
    mi = (lo + hi) // 2
    if check(mi):
        hi = mi
    else:
        lo = mi + 1

print(hi)


Measured memory_bytes: 7088
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

ll ans;
ll N, M;

int main(void) {
    scanf("%lld %lld", &N, &M);
    if (M < N * 2) ans = M / 2;
    else {
        ans = N;
        M -= N*2;
        ans += M/4;
    }
   

  
    printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

int64_t N, K;

void solve()
{
    std::cin >> N >> K;

	int64_t R = N % K;
	int64_t ans = std::min(R, K - R);
	std::cout << ans << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	solve();
}


Measured memory_bytes: 3648
N,M = map(int,input().split())
ans = [-1] * N
chk = 0
for i in range(M):
	s,c = map(int,input().split())
	if ans[s-1] < 0:
		ans[s-1] = c
	elif ans[s-1] == c:
		continue
	else:
		chk = -1
for i in range(N):
		if i == 0:
			if ans[i] == -1:
				if N == 1 and M == 0:
					ans[i] = 0
				else:
					ans[i] = 1
			elif ans[i] == 0:
				if N != 1:
					chk = -1
		else:
			if ans[i] == -1:
				ans[i] = 0
if chk == -1:
	print(-1)
else:
	for i in range(N):
		ans[i] = str(ans[i])
	s = "".join(ans)
	print(s)

Measured memory_bytes: 38492
n,a,b = map(int,input().split())

if n == 1:
  if a == b:
    print(1)
    exit()
  else:
    print(0)
    exit()
elif a > b:
  print(0)
  exit()
else:
  print(((n-1)*b+a)-((n-1)*a+b)+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define cin(a) scanf("%d",&a)
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;

int main()
{
	ll a,n;
	ll b = 0;
	cin>>a>>n;
	ll c;
	for(int i = 1; i <= n; i++) 
	{
		cin>>c;
		b += c;
	}
	if(b >= a) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 384
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] weeks = {"Wednesday","Thursday","Friday","Saturday","Sunday","Monday","Tuesday"};
		int[] monthes = {31,29,31,30,31,30,31,31,30,31,30,31};
		
		String str;

		try {
			while ((str = br.readLine()) != null) {
				String strArray[] = str.split(" ");
				if(Integer.parseInt(strArray[0]) == 0) break;
				int month = 0;
				for(int i = 1; i < Integer.parseInt(strArray[0]); i++ ) {
					month +=  monthes[i - 1];
				}
				int days = Integer.parseInt(strArray[1]);
				
				System.out.println(weeks[(days + month) % 7 ]);
			}
		} catch(IOException e) {
			e.printStackTrace();
		}
	}

}

Measured memory_bytes: 15080
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef long long lint;

int main(){
    bool flag[10010];
    vector<int> p;
    rep(i, 10010) flag[i] = true;
    flag[0] = flag[1] = false;
    rep(i, 10010)if(flag[i]){
        p.push_back(i);
        for(int j=i*2; j<10010; j+=i) flag[j] = false;
    }
    int n;
    while(scanf("%d", &n) && n){
        int cnt = 0;
        int l = 0;
        int r = 0;
        int psum = 0;
        while(l < p.size()){
            while(r < p.size() && psum < n){
                psum += p[r];
                ++r;
            }
            if(psum == n) ++cnt;
            psum -= p[l];
            ++l;
        }
        printf("%d\n", cnt);
    }
}


Measured memory_bytes: 3272
using System;
using System.Collections.Generic;
using static Assistant.Input;
using static Assistant.Debug;
using System.Linq;
using Assistant;

namespace ABC118B
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt;
            var M = ReadInt;
            int[] like = new int[M];
            for (int i = 0; i < N; i++)
            {
                var A = ReadInts;
                for (int j = 1; j <= A[0]; j++)
                {
                    like[A[j] - 1]++;
                }
            }

            int ans = like.Where(x => x >= N).Count();
            Console.WriteLine(ans);
        }


    }


}

namespace Assistant
{
    static class Input
    {
        static List<string> line = new List<string>();
        static int index = 0;
        static String ReadNext()
        {
            if (line.Count <= index) line.AddRange(Console.ReadLine().Split());
            return line[index++];
        }
        public static int ReadInt => int.Parse(ReadNext());
        public static long ReadLong => long.Parse(ReadNext());
        public static int[] ReadInts => Console.ReadLine().Split().Select(int.Parse).ToArray();
        public static long[] NextLongs => Console.ReadLine().Split().Select(long.Parse).ToArray();
    }

    static class Debug
    {
        static public void Draw2D(int[,] map, int mode = 1)
        {
#if DEBUG
            int W = map.GetLength(0);
            int H = map.GetLength(1);

            int[,] map2 = new int[W + 1, H + 1];
            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (i == 0 && j == 0) map2[i, j] = 0;
                    else if (i == 0) map2[i, j] = j - 1;
                    else if (j == 0) map2[i, j] = i - 1;
                    else map2[i, j] = map[i - 1, j - 1];
                }
            }

            for (int i = 0; i < W + 1; i++)
            {
                for (int j = 0; j < H + 1; j++)
                {
                    if (mode == 0) Console.Write(map2[i, j] % 10);
                    if (mode == 1) Console.Write(map2[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
#endif
        }

        static void Draw1D(int[] array, int mode = 0)
        {
#if DEBUG
            Console.WriteLine(string.Join(" ", array));
#endif
        }
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
#include<map>
#define ll long long
using namespace std;
int main(){
	ll n,m;
  cin>>n>>m;
  unordered_map<int,int> checkForCorrect;
  int num;
  string verdict;
  int correctAns=0;
  int pen=0;
  while(m--){
  	cin>>num>>verdict;
    int temp=checkForCorrect[num];
    if(verdict=="AC"){
    	if(temp<=0){
        	correctAns++;
        	pen+=(-temp);
        }
      checkForCorrect[num]=1;
    }
    else{
        if(temp<=0){
            checkForCorrect[num]--;
        }
    }
  }
  cout<<correctAns<<" "<<pen<<endl;
}


Measured memory_bytes: 4388
# Tenka1 Programming Beginner Contest 2019: B – *e**** ********e* *e****e* ****e**
N = int(input())
S = input()
K = int(input())

s_k = S[K - 1]

replaced = ''
for s in S:
    replaced = replaced + '*' if s != s_k else replaced + s_k

print(replaced)

Measured memory_bytes: 9020
import java.awt.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner scanner = new Scanner(System.in);

        int h = scanner.nextInt();
        int w = scanner.nextInt();

        int[][] cost = new int[10][10];
        for (int i = 0; i < 10; i++) {
            Arrays.setAll(cost[i], i1 -> scanner.nextInt());
        }

        for (int i = 0; i < 10; i++) {
            if (i == 1) {
                continue;
            }
            int standard = cost[i][1];
            Deque<Point> stack = new ArrayDeque<>();
            for (int j = 0; j < 10; j++) {
                if (i == j) {
                    continue;
                }
                if (cost[i][j] < cost[i][1]) {
                    stack.addFirst(new Point(j, cost[i][j]));
                }
            }
            while (!stack.isEmpty()) {
                Point p = stack.removeFirst(); // 先頭の座標を取得後、削除
                for (int k = 0; k < 10; k++) {
                    if (p.x == k) {
                        continue;
                    }
                    int v = p.y + cost[p.x][k];
                    if (v < standard) {
                        if (k == 1) {
                            standard = v;
                        } else {
                            stack.add(new Point(k, v));
                        }
                    }
                }
            }
            cost[i][1] = standard;
        }
        long ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int v = scanner.nextInt();
                if (v > - 1) {
                    ans += cost[v][1];
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 56964
#include<bits/stdc++.h>
typedef long long ll ;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull ;
const double PI = acos(-1) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define for0(i,n)          for(int i=0;i<n;i++)
#define for1(i,n)          for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
//#define gcd(a, b)     __gcd(a, b)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
//#define abs(x)		fabs(x)
#define pcase(z,x)     cout<<"Case "<<z<<": "<<x<<"\n"
#define CIN	ios_base::sync_with_stdio(0); cin.tie(0)
#define max 100003

using namespace std;
ll n,m,y,x,a,b,h,e,l,o,i,j;

int main()
{
	
	CIN;
	cin>>n;
	 db p=(sqrt(8*n)-1)*1.0/2;
	p=ceil(p);
	cout<<(ll)p<<nw;

	


}



Measured memory_bytes: 3668
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

a = ns()

if ord(a) > 96:
    print('a')
else:
    print('A')

Measured memory_bytes: 8988
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

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

  int n, h, w; cin >> n >> h >> w;
  


  cout << (n-h+1)*(n-w+1) << endl;

}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
//                  Allah_Almost3aan       
//      *{ربى..  كنْ لىِ خيرَ مدبر فإنى لا احسنُ التدبير}*
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
using ll = long long;
ll mod = 1e9 + 7;
const ll  OO = 1e18;
#define ed "\n"
#define ff first
#define ss second
#define sz(a) a.size()
#define INF 1e9
#define SZ 1000007
#define RT(v) return cout<<v<<ed,0
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define stpr(n) fixed<<setprecision(n)
#define pi 3.14159265358979323846
int di[8] = { 1, 0, -1, 0, -1, 1, -1, 1 };
int dj[8] = { 0, -1, 0, 1, 1, 1, -1, -1 };
const int N = 1.5 * 10000000 + 16;
string ys = "YES", no = "NO";
void fast() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
}
ll fact(ll n)
{
	if (n == 1 || n == 0)return 1;
	else
		return n * fact(n - 1);
}
int main() {
	fast();
	int n; cin >> n;
	vector<pair<int, int>>v(n);
	for (auto &i : v) cin >> i.ff >> i.ss;
	sort(all(v));
	long double sum = 0;
	do{
		for (int i = 1; i < n; i++)
			sum += (sqrt((v[i - 1].ff - v[i].ff)*(v[i - 1].ff - v[i].ff)
			+ (v[i - 1].ss - v[i].ss)*(v[i - 1].ss - v[i].ss)));
	  } while (next_permutation(all(v)));
	cout <<stpr(10)<< sum / fact(n) << ed;
}


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

int main()
{
    string s;
    cin >> s;
    if (s == "Sunny") printf("Cloudy\n");
    if (s == "Cloudy") printf("Rainy\n");
    if (s == "Rainy") printf("Sunny\n");
    return 0;
}

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

class Solution
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var p = new long[n];
        var existOnLefts = new bool[n + 1];
        var chained = new bool[n + 1];
        for (int i = 0; i < n; i++)
        {
            var v = int.Parse(Console.ReadLine());
            p[i] = v;
            existOnLefts[v] = true;

            if (v > 1)
            {
                if (existOnLefts[v - 1])
                {
                    chained[v] = true;
                }
            }
        }

        var maxChain = 1;
        var curChain = 1;
        for (int v = 1; v <= n; v++)
        {
            if (chained[v])
            {
                curChain++;
                if (maxChain < curChain)
                {
                    maxChain = curChain;
                }
            }
            else
            {
                curChain = 1;
            }
        }

        Console.WriteLine(n - maxChain);
    }
}

Measured memory_bytes: 16988
#include <stdio.h>
#include <string.h>
int main()
{
 
    int i ;
    char s[100], p[100] ,ss[201] ;



	scanf("%s", s);
	scanf("%s", p);

	strcat( ss, s );
	strcat( ss, s );


	if ( strstr( ss , p ) != '\0' )
		printf("Yes\n") ;
	else 
		printf("No\n") ;
return 0;
}

Measured memory_bytes: 532
def gcd(x,y):
    x, y = max(x,y), min(x,y)
    while x!=0 :
        x, y = max(x,y), min(x,y)
        x %= y
    return y
#print(gcd(4,8))

a,b,c,d = map(int,input().split())
c_ok = b//c - (a-1)//c
d_ok = b//d - (a-1)//d

cd = int(c*d/gcd(c,d))
cd_ok = b//cd - (a-1)//cd

print(int(b-a+1-c_ok-d_ok+cd_ok))

Measured memory_bytes: 38476
import java.util.*;
public class Main {
	public static void main(String[] args){
    //データ取り込み
		Scanner sc = new Scanner(System.in);
		//String S = sc.next();
    //int B = sc.nextInt();
    //System.out.println();
		int N = sc.nextInt();
		
		System.out.println(24+24-N);
	}
}

Measured memory_bytes: 22612
const line = require('fs').readFileSync('/dev/stdin', 'utf-8').split('\n');

const data = line[1].split(' ').map(Number);

data.map((x, i, arr) => {
    const p = Math.floor((i+1) / 2);
    const l = (i+1) * 2;
    const r = l + 1;

    const pStr = p > 0 ? `parent key = ${arr[p-1]}, ` : '';
    const lStr = l <= arr.length ? `left key = ${arr[l-1]}, ` : '';
    const rStr = r <= arr.length ? `right key = ${arr[r-1]}, ` : ''

    return [`node ${i+1}: key = ${x}, `, pStr, lStr, rStr].join('');
})
.forEach(x => console.log(x));



Measured memory_bytes: 17372
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

#define MIN 1E9
#define MAX -10000000

int main(void){
    int n,a[10100];
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int ans=0;
    for(int i=0;i<n;i++){
        int sum=0;
        while(a[i]%2==0){
            a[i]/=2;
            sum++;
        }
        ans+=sum;
    }
    printf("%d",ans);
    return 0;
}


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

namespace ProgramingStudying2
{
    class Program
    {

        static void Main(string[] args)
        {
            var x = int.Parse(Console.ReadLine());
            var factors = new List<int>();

            for(int i = 1; i <= Math.Sqrt(x); i++)
            {
                if(x % i == 0)
                {
                    factors.Add(i);
                }
            }
            foreach(var factor in factors)
            {
                var b = -factor / 2;
                while (Math.Pow(b + factor, 5) - Math.Pow(b, 5) <= x) 
                {
                    if(Math.Pow(b + factor, 5) - Math.Pow(b, 5) == x)
                    {
                        Console.WriteLine("{0} {1}", b + factor, b);
                        return;
                    }
                    b++;
                }
            }
        }
    }
}


Measured memory_bytes: 27968
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 100000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;

template<typename T>
void invec(vector<T> &A){rep(i, 0, A.size()) cin >> A[i];}

struct edge {int to, cost;};
template <typename T>
bool chmin(T &a, const T& b) {if (a > b) {a = b; return true;} return false;}

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

int N, Q, K; cin >> N;
VI a(N-1), b(N-1), c(N-1);
vector<vector<edge>> G(N+1);
rep(i, 0, N-1){ 
    int a;
    edge e; cin >> a >> e.to >> e.cost;
    G[a].emplace_back(e);
    swap(a, e.to);
    G[a].emplace_back(e); 
}

cin >> Q >> K;

// K からの最短経路. dijkstra.
VI d(N+1, INF); // d[i] = 頂点 s から i への最短距離
d[K] = 0;

priority_queue<PII, VP, greater<PII>> q; 
q.emplace(PII(0, K));

while(!q.empty()){
    PII p = q.top(); q.pop();
    int v = p.second;
    if (d[v] < p.first) continue; 
    for (edge e: G[v])
        if (chmin(d[e.to], d[v] + e.cost))
            q.emplace(PII(d[e.to], e.to));
}

rep(_, 0, Q) {
    int x, y; cin >> x >> y;
    cout << d[x] + d[y] << "\n";
}


}
// 書いて考える．場合分け
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 12400
/*
 Author : Bisma
 @ copy from bisma template 1.0
 */
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <iomanip>
#include <fstream>
#include <cstdio>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define repn(a,b,c) for(int a=b; a>=c; a--)
#define ll long long
#define mem(a, b) memset(a, (b), sizeof(a))
#define loop(a,b,c) for(int a = b ;a<c;a++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;

ll max(ll a, ll b){
    if(a>b) return a;
    return b;
}

ll min(ll a, ll b){
    if(a>b) return b;
    return a;
}

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}



int main(){
    fast();

    
    string s,a;

    ll n;


    s = "0";

    cin>>n>>a;

    ll k;

    cin>>k;

    s+=a;

    char p = s[k];


    rep(i,1,n){
        if(s[i]!=p){
            cout<<"*";
        }else{
            cout<<s[i];
        }
    }

    cout<<endl;

    return 0;
    
}
 






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

using namespace std;

int main()
{
  string c[3];
  cin>> c[0];
  cin>> c[1];
  cin>> c[2];

  cout<< c[0][0]<< c[1][1]<< c[2][2]<< endl;


  return 0;
}


Measured memory_bytes: 764
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int d = sc.nextInt();
    int t = sc.nextInt();
    int s = sc.nextInt();
    String ans;
    if (t * s < d) {
      ans = "No";
    } else {
      ans = "Yes";
    }
    System.out.println(ans);
    sc.close();
  }
}

Measured memory_bytes: 35720
#include<stdio.h>
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int a[n];
    int big;
    int sum=0;
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        sum=sum+a[i];
    }
//    printf("%d sum\n",sum);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]<a[j]){
                big=a[i];
                a[i]=a[j];
                a[j]=big;
            }
        }
    }
  /*  for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }*/
    //printf(" array \n");
    for(int i=0;i<m;i++){
        if(a[i]*4*m<sum){
            printf("No");
            return 0;
        }
        else if(i==(m-1)){
            printf("Yes");
            return 0;
        }
    }
}



Measured memory_bytes: 1712
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 



int main()
{ 
    int k;
    int a, b, m, n;
    cin >> k >> a >> b;
    m = a/k;
    n = b/k;

    
    
        if (a != b)
        {
            if (n > m)
            {
                cout << "OK";
            }
            else
            {
                if (a % k == 0)
                {
                    cout << "OK";
                }
                else
                {
                    cout << "NG";
                }
            }
        }
        else
        {
            if (a % k == 0)
            {
                cout << "OK";
            }
            else
            {
                cout << "NG";
            }
        }
    



    return 0;
    
}




Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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 int INF = 1e9;
const LL LLINF = 1e16;

/*
!) 0-indexed
!) [a, b)に対する演算
!) merge, updateNodeを書く
*/
template<typename Monoid>
struct Segtree{
  private:
    int n;
    vector<Monoid> dat;
    Monoid m0; // データの初期化値

    Monoid merge(Monoid a, Monoid b){ return a | b; }
    void updateNode(int k, Monoid x){ dat[k] = x; }

  public:
    Segtree(int sz, Monoid m0) : m0(m0){
        n = 1;
        while(n < sz) n *= 2;
        dat.assign(2*n-1, m0);
    }

    void update(int k, Monoid x){
        k += n-1;
        updateNode(k, x);
        while(k > 0) {
            k = (k-1)/2;
            dat[k] = merge(dat[k*2+1], dat[k*2+2]);
        }
    }
    Monoid query(int a, int b){
        Monoid L = m0, R = m0;
        int A = a+n-1;
        int B = b+n-1;
        while(A < B) {
            if((A&1) == 0) L = merge(L, dat[A++]);
            if((B&1) == 0) R = merge(dat[--B], R);
            A >>= 1;
            B >>= 1;
        }
        return merge(L, R);
    }
    Monoid operator[](const int &k) const { return dat[k+n-1]; }
};

int main(){
    fastcin();
    int n;
    cin >> n;
    string s;
    cin >> s;
    Segtree<LL> seg(n, 0);
    rep(i, n){
        seg.update(i, (1<<(s[i]-'a')));
    }
    int q;
    cin >> q;
    rep(i, q){
        int tp;
        cin >> tp;
        if(tp == 1){
            int k;
            char c;
            cin >> k >> c;
            k--;
            seg.update(k, (1<<(c-'a')));
        }else{
            int l, r;
            cin >> l >> r;
            l--;
            cout << __builtin_popcount(seg.query(l, r)) << endl;
        }
    }

}


Measured memory_bytes: 9116
#include<iostream>
using namespace std;
int main(){
    string s;
    cin >> s;
    if((s[0] == s[1] && s[1] == s[2]) || (s[1] == s[2] && s[2] == s[3]))
    {
      cout<<"Yes";
    }
    else
    {
      cout<<"No";
    }
   
  return 0;
}

Measured memory_bytes: 256
s = input()
n = len(s)
s1 = s[0:int(((n-1)/2))]
s2 = s[int(((n+3)/2)-1)::]
if (s != s[::-1]) or (s1 != s1[::-1]) or (s2 != s2[::-1]):
    print('No')
else:
    print('Yes')

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ld = long double;
const ld eps = 1e-9;

int AMAX = 1e5;
int main() {
	int N, M; cin >> N >> M;
	vector<int>nums(AMAX+1);
	for (int i = 0; i < N; ++i) {
		int x; cin >> x;
		nums[x]++;
	}
	vector<pair<int, int>>divides(M);
	for (int i = 0; i <= AMAX; ++i) {
		int di = i%M;
		divides[di].first += nums[i];
		divides[di].second += nums[i]/2;
	}
	int ans = 0;
	for (int i = 0; i <= M / 2; ++i) {
		if (i == 0 || i * 2 == M) {
			int p_num = divides[i].first / 2;
			ans += p_num;
			divides[i].first -= p_num*2;
		}
		else {
			int p_num = min(divides[i].first, divides[M - i].first);
			ans += p_num;
			divides[i].first -= p_num;
			divides[M - i].first -= p_num;
		}
	}
	for (int i = 0; i < M; ++i) {
		ans += min(divides[i].first / 2, divides[i].second);
		
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1408
# include <stdio.h>
# include <vector>

using namespace std;

using ll = long long;

void max_self(ll& a, ll b) {
	a = max(a, b);
}

int main() {
	int n, W;
	scanf("%d%d", &n, &W);
	vector<ll> dp(W+1);
	for (int i=0;i<n;i++) {
		int weight, value;
		scanf("%d%d", &weight, &value);
		for (int j=W-weight;j>=0;j--) {
			max_self(dp[weight+j], dp[j] + value);
		}
	}
	ll ans = 0;
	for (int i=0;i<=W;i++) {
		max_self(ans, dp[i]);
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1024
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))

I="IMPOSSIBLE"
P="POSSIBLE"

if max(a)<k:
    print(I)
    quit()

gcd=a[0]
for i in range(n):
    gcd=math.gcd(gcd,a[i])

if k%gcd==0:
    print(P)
else:
    print(I)

Measured memory_bytes: 89624
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define pdump(p) cout<<" "<<#p<<"=("<<p.fst<<","<<p.snd<<")"
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std; using lint = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<lint, lint>;

int main(void) {
    int n; cin >> n;
    int t, a; cin >> t >> a;
    t *= 1000; a*= 1000;
    int gap = 1e9;
    int ans = 1e9;
    
    repeat (i, n) {
        int h;
        cin >> h;
        int tmp = t - h * 6;
        //dump(tmp); dump(abs(a-tmp)); dump(gap); el;
        if (abs(a - tmp) < gap) {
            gap = abs(a - tmp);
            ans = i;
        }
    }
    cout << ans + 1 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

#define MOD 1000000007

int f[200005];
int val[200005];
int a[200005];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == a[i-1]) {
            f[i] = f[i-1]; continue;
        }
        val[a[i]] += f[i-1];
        if (val[a[i]] >= MOD) val[a[i]] -= MOD;
        f[i] = val[a[i]];
    }
    printf("%d", f[n]);
    return 0;
}


Measured memory_bytes: 5552
import java.util.Scanner;

public class Main {
  public static void main(final String[] args) {

    Scanner sc = new Scanner(System.in);
    int iNum = sc.nextInt();
    sc.nextLine();
    String sValue = sc.nextLine();
    String sCost = sc.nextLine();
    String[] sSplitVal = sValue.split(" ");
    String[] sSplitCost = sCost.split(" ");
    int iResult = 0;
    for (int ii = 0; ii < iNum; ii++) {
      int iVal = Integer.parseInt(sSplitVal[ii]);
      int iCost = Integer.parseInt(sSplitCost[ii]);
      int iCalc = iVal - iCost;
      if (0 < iCalc) {
        iResult += iCalc;
      }
    }
    System.out.print(iResult);
  }
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
#define db(x) cout << #x << " = " << (x) << "\n";
using ll = long long;
using ld = long double;
ll nodes, edges;
vector<ll> dist;
vector<ll> visited;
vector<ll> in_degree;
vector<vector<ll>> v;
void topological_sort()
{
    vector<bool> visited(nodes + 1, false);
    queue<ll> q;
    for (ll i = 1; i <= nodes; i++)
    {
        if (!in_degree[i])
        {
            q.push(i);
            visited[i] = true;
        }
    }
    while (!q.empty())
    {
        ll vertex = q.front();
        q.pop();
        for (ll i : v[vertex])
        {
            dist[i] = max(dist[i], dist[vertex] + 1);
            if (!visited[i])
            {
                in_degree[i]--;
                if (!in_degree[i])
                {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> nodes >> edges;
    ll from, to;
    v.resize(nodes + 1);
    in_degree.resize(nodes + 1);
    visited.resize(nodes + 1);
    dist.resize(nodes + 1);
    for (ll i = 0; i < edges; i++)
    {
        cin >> from >> to;
        v[from].push_back(to);
        ++in_degree[to];
    }
    topological_sort();
    cout << *max_element(dist.begin(), dist.end());
    return 0;
}


Measured memory_bytes: 8064
A, B, C, X, Y = map(int, input().split())
if A + B <= C * 2:
    print(A * X + B * Y)
else:
    if X >= Y:
        if A >= 2 * C:
            print(C * Y * 2 + 2 * C * (X - Y))
        else:
            print(C * Y * 2 + A * (X - Y))
    else:
        if B >= 2 * C:
            print(C * X * 2 + 2 * C * (Y - X))
        else:
            print(C * X * 2 + B * (Y - X))


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
	int w, h, x, y, r;
	cin >> w >> h >> x >> y >> r;
	pair<int, int> xy[4] = { {x - r,y - r},{x - r,y + r},{x + r,y - r},{x + r,y + r} };
	for (int i = 0; i < 4; i++)
	{
		if (!(xy[i].first >= 0 && xy[i].first <= w && xy[i].second >= 0 && xy[i].second <= h))
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;

	return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int A = nextInt();
  int B = nextInt();
  if (A > B) swap(A, B);
  if ((B - A) % 2 == 1) {
    cout << "IMPOSSIBLE" << endl;
  } else {
    cout << (A+B)/2 << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
   string s="CODEFESTIVAL2016";
  string s1;
  cin>>s1;
  int i,cnt=0;
  for(i=0;i<s1.length();++i)
  {
    if(s1[i]!=s[i])
       cnt++;
  }
  
  printf("%d",cnt);
   
   
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int[][] F=new int[N][10];
        for(int i=0;i<N;i++){
            for(int j=0;j<10;j++){
                F[i][j]=sc.nextInt();
            }
        }
        int[][] P=new int[N][11];
        for(int i=0;i<N;i++){
            for(int j=0;j<11;j++){
                P[i][j]=sc.nextInt();
            }
        }
        
        int ans=0;
        int[] O=new int[10];
        for(int k=1;k<=1023;k++){
            int pre=0;
            for(int i=0;i<10;i++){
                O[i]=k/((int)Math.pow(2,i))%2;
            }
            int[] dup=new int[N];
            for(int i=0;i<N;i++){
                dup[i]=0;
                for(int j=0;j<10;j++){
                    dup[i]+=O[j]*F[i][j];
                }
            }
            for(int i=0;i<N;i++){
                pre+=P[i][dup[i]];
            }
            if(k==1){
                ans=pre;
            }else if(pre>ans){
                ans=pre;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 28196
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		String s = sc.next();
		// AKIHABARA
		if (s.matches("A?KIHA?BA?RA?")) {
			System.out.println("YES");

		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21844
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"s = input()\n"
"a = 0\n"
"for i in s:\n"
"    a += int(i)\n"
"if int(s) % a == 0:\n"
"    print('Yes')\n"
"else:\n"
"    print('No')\n"
"\"";
  system(s);
  return 0;
}            

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

int main(){
  int x1,y1,x2,y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int x3=x2+y1-y2;
  int y3=-x1+x2+y2;
  int x4=x1+y1-y2;
  int y4=-x1+x2+y1;
 
  cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;
#define N (1<<17)
class RAQxRMQ{
private:
    ll dat[N*2],laz[N*2];
    void eval(int k){
	dat[k]+=laz[k];
	if(k<N-1){
	    laz[k*2+1]+=laz[k];
	    laz[k*2+2]+=laz[k];
	}
	laz[k]=0;
    }
    ll dfs(int l,int r,int a,int b,int k){
	eval(k);
	if(l<=a&&b<=r)return dat[k];
	if(b<=l||r<=a)return (ll)mod*(ll)mod;
	ll vl=dfs(l,r,a,(a+b)/2,k*2+1);
	ll vr=dfs(l,r,(a+b)/2,b,k*2+2);
	return min(vl,vr);
    }
    void ufs(int l,int r,int a,int b,int k,ll x){
	//eval(k);
	if(l<=a&&b<=r){laz[k]+=x;eval(k);return;}
	if(b<=l||r<=a){eval(k);return;}
	eval(k);
	ufs(l,r,a,(a+b)/2,k*2+1,x);
	ufs(l,r,(a+b)/2,b,k*2+2,x);
	dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
public:
    void Init(){
	lol(i,2*N)dat[i]=laz[i]=0;
    }
    void Add(int l,int r,ll x){
	ufs(l,r+1,0,N,0,x);
    }
    ll Min(int l,int r){
	return dfs(l,r+1,0,N,0);
    }
};
int main(){
    int n,q;cin>>n>>q;
    RAQxRMQ seg;seg.Init();
    while(q--){
	ll z,a,b,c;
	cin>>z;
	if(z==0){
	    cin>>a>>b>>c;
	    seg.Add(a,b,c);
	}
	if(z==1){
	    cin>>a>>b;
	    cout<<seg.Min(a,b)<<endl;
	}
    }
    return 0;
}



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

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

    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

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

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

int main(){
    double A,B,H,M;
    cin >> A >> B >> H >> M;
    double rad = min(abs(30 * H + 0.5 * M- 6 * M), abs(30 * H + 0.5 * M- 6 * M));
	//rad = rad/360*2*M_PI;

    double ans;
    if(rad == 0) {
        ans = abs(A-B);
    }else if(rad == 180){
      	ans = A + B;
    }else{
        ans = sqrt(A*A + B*B -2*A*B*cos(rad/360*2*M_PI));
    }
    cout << fixed << setprecision(20) << ans << endl;
}

Measured memory_bytes: 4084
#pragma region Header

#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <numeric>
#include <bitset>
#include <cstdint>
#include <stdexcept>
using namespace std;

// 整数型

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

// [0,n)を昇順/降順でループ

#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)

// [a,b)を昇順/降順でループ

#define FOR(i, a, b) for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define FORD(i, a, b) for (int i = static_cast<int>(b) - 1; i >= static_cast<int>(a); --i)

template <typename T>
int SZ(T x)
{
    return static_cast<int>(x.size());
}

#pragma endregion

int solve(vector<int> d_s, int n, int x, int m)
{
    int k = d_s.size();
    int zeros_d = 0;
    i64 sum_d = 0;
    rep(i, k)
    {
        d_s[i] %= m;
        sum_d += d_s[i];
        if (d_s[i] == 0)
        {
            ++zeros_d;
        }
    }
    x %= m;

    i64 rem = 0;
    int rem_zeros = 0;
    rep(i, (n - 1) % k)
    {
        rem += d_s[i];
        if (d_s[i] == 0)
        {
            ++rem_zeros;
        }
    }

    i64 last = x + ((n - 1) / k) * sum_d + rem;
    i64 zeros = ((n - 1) / k) * zeros_d + rem_zeros;
    return n - 1 - zeros - last / m;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int k, q;
    cin >> k >> q;
    vector<int> d_s(k);
    rep(i, k)
    {
        cin >> d_s[i];
    }
    rep(i, q)
    {
        int n, x, m;
        cin >> n >> x >> m;
        cout << solve(d_s, n, x, m) << '\n';
    }

    return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mp make_pair
#define pb push_back
#define size(type) ((char *)(&type+1)-(char*)(&type))
#include <bits/stdc++.h> 
using namespace std; 
int main(){
  int x;
  cin>>x;
  if(x==0){
  cout<<1<<"\n";}
  else{
  cout<<0<<"\n";}
return 0;}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a); i >= (b); --i)
#define sz(a) int((a).size())
#define pconent(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef long double ld;
const ll MOD =  998244353;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(v) (cerr<<#v<<" ** "<<v<<" ** "<<endl)
template <class T> inline void dbv(T a) { for(auto x : a){ cout<<x<<" ** " ;} cout<<endl;}
vector<ll> fact;
vector<ll> bin;
ll n ;
void pre()
{
    fact.resize(n+5,1);
    bin.resize(n+5,1);
    FOR(i,1,n+5)
    {
        fact[i] = (i*fact[i-1])%MOD;
    }
    FOR(i,0,n+1)
    {
        bin[i] = (fact[n]*inv((fact[n-i]*fact[i])%MOD))%MOD;
    }
}
void output(ll tx)
{
    ll a,b,k;
    cin>>n>>a>>b>>k;
    pre();
    ll ans = 0;
    FOR(i,0,n+1)
    {
        ll ca = i;
        ll cb;
        if((k-ca*a)>=0 && (k-ca*a)%b==0)
        {
            // db(ca);
            cb = (k-ca*a)/b;
        }
        else
        {
            continue;
        }
        if(max(ca,cb)>n)
        {
            continue;
        }
        ll x = ca;
        ll y = cb;
        ll temp = (bin[ca]*bin[cb])%MOD;
        ans = (ans+temp)%MOD;
        // FOR(j,max((ll)0,ca+cb-n),min(x,y)+1)
        // {
        //     ll fx = x-j;
        //     ll fy = y-j;
        //     ll fj = j;
        //     ll temp = fact[n];
        //     temp = (temp*inv(fact[n-fx-fy-j]))%MOD;
        //     temp = (temp*inv(fact[j]))%MOD;
        //     temp = (temp*inv(fact[fx]))%MOD;
        //     temp = (temp*inv(fact[fy]))%MOD;
        //     // db(temp);
        //     ans = (ans+temp)%MOD;
        // }
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t =1;
    // cin>>t;
    FOR(i,0,t)
    {
        output(i+1) ;
    }
    return 0 ;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define toup toupper
#define tolow tolower
const int mod = 1000000;
const int maxn = 10000;
typedef long long ll;
using namespace std;

int length(ll n){
	return (int)log10(n) + 1;
}

ll quickpow(ll x, ll y){
	ll res = 1;
	while(y){
		if(y & 1) res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

ll fac(ll x){
	if(x == 0 || x == 1) return 1;
	return x * fac(x - 1);//mod
}

bool isprime(int n){
	bool flag = true;
	for(int i = 2; i <= sqrt(n); i++){
		if(n % i == 0) flag = false;
	}
	return flag;
}


int main(){
   int t;
   ll a,b,pro;
   ll sq,res=0;
   cin>>t;
   while(t--){
      cin >> a >> b;
      pro = a * b;
      sq = sqrt(pro);
      res = sq * 2;
       if(sq * sq == pro)
       {
       	   res -= 2;
       }
       else if((pro-1)/sq==sq)
       {
           res--;
       }
 
       if(!(a == b && b == sq))
       {
           res--;
       }
 
       cout<<res<<endl;
   }
    return 0;
}

Measured memory_bytes: 256