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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,d;
    cin >> n >> d;
    ll ans = 0;
    for(i = 0;i < n;++i){
        ll x,y;
        cin >> x >> y;
        ll tmp = x*x + y*y;
        if(tmp <= d*d) ++ans;
    }
    cout << ans << endl;

    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define lf double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

bool isPrime(ll x)
{
	for(int i=2; i*i<=x; i++)
		if (x%i==0) return false;
	return true;
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n; cin>>n;
	ll ans=0;
	rep(i, n){
		ll x; cin>>x;
		if (isPrime(x)) ans++;
	}
	cout << ans << "\n";
	return 0;
}


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

const int maxn = 20; 

typedef long long ll; 

int n, SUM;
int d[maxn];
ll C[maxn][maxn]; 
ll Pow[maxn][maxn]; 
ll ans, PROD; 
int a[maxn]; 
int b[maxn]; 
/*
void solve1() {
	memset( f, 0, sizeof( f ) ); 
	f[0][0] = 1; 
	for (int i = 1; i <= n; ++i) 
		for (int j = 0; j <= n * 9; ++j) 
			for (int k = 0; k <= min(j,9); ++k) 
				f[i][j] += f[i-1][j-k];
	for (int i = 0; i < SUM; ++i) ans += f[n][SUM]; 
}*/

ll Count() {
	//cout<<b[0]<<' '<<b[1]<<' '<<b[2]<<endl; 
	int all = 0; 
	ll ret = 1; 
	for (int i = 0; i <= 9; ++i) {
		if ( b[i] < 0 ) return 0; 
		all += b[i]; 
		ret *= C[all][b[i]]; 
	}
	return ret; 
}

void dfs(int dep, int left, int sum, ll prod) {
	if ( dep > 9 ) {
		if ( left == 0 ) {
			for (int i = 0; i <= 9; ++i) b[i] = a[i]; 
			if ( sum < SUM || prod < PROD ) ans += Count(); 
			else if ( prod == PROD ) {
				for (int i = 1; i <= n; ++i) {
					if ( i != 1 ) b[d[i-1]]--;
					for (int j = 0; j < d[i]; ++j) {
						b[j]--; 
						ans += Count(); 
						b[j]++; 
					}
				} 
			}
		}
		return; 
	}
	for (int i = 0; i <= left; ++i) 
		if ( i * dep + sum <= SUM ) {//&& prod*Pow[i+1][dep] <= PROD ) {
			a[dep] = i; 
			dfs( dep+1, left-i, sum+i*dep, prod*Pow[dep+1][i] );
		}
}

void Init() {
	memset( C, 0, sizeof( C ) ); 
	C[0][0] = 1; 
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1; 
		for (int j = 1; j <= n; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j]; 
	}
	for (int i = 1; i <= 10; ++i) {
		Pow[i][0] = 1; 
		for (int j = 1; j <= n; ++j)
			Pow[i][j] = Pow[i][j-1] * i; 
	}
}

int main() {
	char st[maxn]; 
	cin>>st; 
	n = strlen( st ); 
	for (int i = 1; i <= n; ++i) d[i] = st[i-1] - '0'; 
	SUM = 0; 
	for (int i = 1; i <= n; ++i) SUM += d[i]; 
	PROD = 1;
	for (int i = 1; i <= n; ++i) PROD *= ( d[i] + 1 ); 
	Init(); 
	ans = 0;
	dfs( 0, n, 0, 1 ); 
	cout<<ans<<endl; 
}

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

int main() {

	int n; cin >> n;
	vector<int> b(n - 1);
	for (int i = 0; i < n - 1; i++) {
		cin >> b[i];
	}
	int ans = b[0] + b[n - 2];
	for (int i = 1; i < n - 1; i++) {
		ans += min(b[i - 1], b[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if (s < t)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 3632
from collections import Counter

def euclid(x, y):
    r = x % y
    if r == 0:
        return y
    else:
        return euclid(y, r)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

A, B = map(int, input().split())
if A > B:
    A, B = B, A
print(len(Counter(prime_factorize(euclid(A, B)))) + 1)


Measured memory_bytes: 38512
n, m = map(int, input().split())
A = [list(map(int, input().split())) for i in range(m)]

B = [[] for i in range(n + 1)]

for i in range(m):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])

co = 0
ok = 0
while ok == 0:
    ok = 1
    for i in range(1, n + 1):
        if len(B[i]) == 1:
            ok = 0
            k = B[i][0]
            B[i].remove(k)
            B[k].remove(i)
            co += 1

print(co)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

struct BIT{
  int size;
  vector<ll> dat;
  void init(int n){
    size=n;
    dat.clear();
    dat.resize(n+1);
  }
  void add(int i,ll x){
    while(i<=size){
      dat[i]+=x;
      i +=i&-i;
    }
  }
  ll sum(int i){
    ll s=0;
    while(0<i){
      s +=dat[i];
      i -=i&-i;
    }
    return s;
  }
};

pair<int,pint> p[300001];
int main(){
    int n,m,l,r;
    cin>>n>>m;
    BIT b1,b2;
    b1.init(m);
    b2.init(m);
    rep(i,n){
        cin>>l>>r;
        p[i]=mp(r-l+1,mp(l,r));
    }
    sort(p,p+n);
    int x=1,cnt=0;
    FOR(i,1,m+1){
        while(cnt<n&&p[cnt].first<i){
            l=p[cnt].second.first,r=p[cnt].second.second;
            b1.add(l,x);
            b2.add(l,-x*(l-1));
            b1.add(r,-x);
            b2.add(r,x*r);
            ++cnt;
        }
        int ans=n-cnt;
        for(int j=0;j<=m;j+=i) ans+=b1.sum(j)*j+b2.sum(j)-b1.sum(j-1)*(j-1)-b2.sum(j-1); 
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 6016
#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll div_ceil(ll, ll);

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

int main() {
  int r, D, x;
  std::cin >> r >> D >> x;
  REP(i, 10) {
    x = r * x - D;
    std::cout << x << '\n';
  }
}

ll div_ceil(ll a, ll b) {
  ll quotient = a / b;
  ll remainder = a % b;
  if (remainder == 0) {
    return quotient;
  } else {
    return quotient + 1;
  }
}


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

int main() {
  // 頂点数と辺数
  int N, M;
  cin >> N >> M;

  // グラフ入力受取
  Graph G(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--; // 0-indexed
    G.at(a).push_back(b);
    G.at(b).push_back(a);
  }

  // BFS のためのデータ構造
  vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
  queue<int> que;

  // 初期条件（部屋1は洞窟の入り口がある特別な部屋）
  dist[0] = 0;
  que.push(0); // 0 を橙色頂点にする

  // BFS 開始（キューが空になるまで探索を行う）
  while (!que.empty()) {
    int v = que.front(); // キューから先頭頂点を取り出す
    que.pop();

    // v から辿れる頂点をすべて調べる
    for (int nv : G[v]) {
      if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

      // 新たな白色頂点 nv について、最短経路で帰れる部屋番号をセットする
      dist[nv] = v;
      que.push(nv);
    }
  }

  // 結果出力
  for (int v = 0; v < N; v++) {
    if (dist[v] == -1) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  for (int v = 1; v < N; v++) {
    cout << dist[v] + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 10232
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    chars = "ACGT"

    if n == 3:
        print(61)
        sys.exit()
    elif n == 4:
        print(230)
        sys.exit()

    from collections import deque, Counter
    que = deque()

    for ch1 in chars:
        for ch2 in chars:
            que.append((ch1 + ch2, 2))

    ans = 0
    str_set = set()
    counter = Counter()

    while que:
        cur, length = que.popleft()
        length_next = length + 1
        for ch in chars:
            ok = True
            nx = cur + ch
            if length_next == 3:
                if "AGC" in nx:
                    continue
                for j in range(2):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    que.append((nx, length_next))
            if length_next == 4:
                if "AGC" in nx:
                    ok = False
                for j in range(3):
                    sl = list(nx)
                    sl[j], sl[j + 1] = sl[j + 1], sl[j]
                    swap = "".join(sl)
                    if "AGC" in swap:
                        ok = False
                if ok:
                    counter[nx] += 1
                    str_set.add(nx)

    for _ in range(n - 4):
        counter_next = Counter()
        for st in str_set:
            for ch in chars:
                nx = st[1:] + ch
                if nx in str_set:
                    counter_next[nx] += counter[st]
                    counter_next[nx] %= MOD
        counter = counter_next

    ans = sum(counter.values())
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 68652
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int cnt[200200];
int p[200200];
int main(){
	
	ll n,m; cin>>n>>m;
	ll ac = 0, pen = 0;
	for(int i = 0; i < m; i++){
		int x;
		string y;
		cin>>x>>y;
		if(y == "WA" && !p[x]) cnt[x]++;
		if(y == "AC" && !p[x]) {
			ac++;
			p[x] = 1;
		}
	}
	for(int i = 0; i < 200200; i++) {
		if(cnt[i] && p[i]) pen += cnt[i]; 
	}
	cout<<ac<<" "<<pen<<"\n";
	
}

Measured memory_bytes: 1024
#include <limits.h>
#include <math.h>
#include <stdio.h>

int main(void) {
  int m,d;
  int nm,nd;
  int ans=0;
  scanf("%d %d",&m,&d);
  scanf("%d %d",&nm,&nd);
  if(m!=nm)ans=1;
  printf("%d\n",ans);
  
  return 0;
}

Measured memory_bytes: 128
def inpl(): return map(int, input().split())
W, H, N = inpl()
a = [0, W, 0, H]
for i in range(N):
    x, y, a_i = inpl()
    if a_i == 1:
        a[0] = max(a[0], x)
    elif a_i == 2:
        a[1] = min(a[1], x)
    elif a_i == 3:
        a[2] = max(a[2], y)
    else:
        a[3] = min(a[3], y)

if a[0]<a[1] and a[2]<a[3]:
    print((a[1]-a[0])*(a[3]-a[2]))
else:
    print(0)

Measured memory_bytes: 3064
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

//const long long int MOD = 1000000007;
const int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> M;
	vector<vector<int>>edge(N);
	vector<vector<int>>index(N, vector<int>(N, -1));
	for (int i = 0; i < M; i++) {
		cin >> L >> R;
		L--;
		R--;
		edge[L].push_back(R);
		index[L][R] = i;
	}
	vector<string>ans(M);
	vector<int>num(M);
	vector<vector<int>>connect(N, vector<int>(N));
	queue<int>Q;
	for (int i = 0; i < N; i++) {
		Q.push(i);
		connect[i][i] = 1;
		while (!Q.empty()) {
			int cn = Q.front();
			Q.pop();
			for (auto j : edge[cn]) {
				if (connect[i][j])continue;
				connect[i][j] = 1;
				Q.push(j);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		vector<int>visit(N);
		visit[i] = 1;
		for (auto j : edge[i]) {
			if (visit[j])num[index[i][j]] = 1;
			else {
				visit[j] = 1;
				Q.push(j);
				while (!Q.empty()) {
					int cn = Q.front();
					Q.pop();
					for (auto k : edge[cn]) {
						if (visit[k])continue;
						visit[k] = 1;
						Q.push(k);
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		vector<int>visit(N);
		visit[i] = 1;
		reverse(edge[i].begin(), edge[i].end());
		for (auto j : edge[i]) {
			if (visit[j])num[index[i][j]] = 1;
			else {
				visit[j] = 1;
				Q.push(j);
				while (!Q.empty()) {
					int cn = Q.front();
					Q.pop();
					for (auto k : edge[cn]) {
						if (visit[k])continue;
						visit[k] = 1;
						Q.push(k);
					}
				}
			}
		}
	}
	for (int i = 0; i < N; i++) {
		for (auto j : edge[i]) {
			num[index[i][j]] -= connect[j][i];
		}
	}
	for (int i = 0; i < M; i++) {
		cout << (num[i] ? "diff" : "same") << endl;
	}
	return 0;
}

Measured memory_bytes: 13312
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S;
  int N=0;
  cin>>S;
  
 
  
  if(S.at(3)==S.at(2)&&S.at(4)==S.at(5)){
    N=1;
  }
  
   if(N==1){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}




Measured memory_bytes: 256
N = int(input())
num_list = list(map(int, input().split()))

max_i = num_list[0]
flag = True
for i in num_list:
  if (max_i - i) >= 2:
    print('No')
    flag = False
    break
    
  if i > max_i:
    max_i = i
    
if flag:
  print('Yes')

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


const int N = 1e5 + 123;
int n, d[N], a[N];
int main() {
	//freopen("input.txt", "r", stdin);
    cin >> n;
    int x, y;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        if(i == 2) {
        	d[i] = abs(a[i - 1] - a[i]);
        }
        if(i > 2) d[i] = min(abs(a[i] - a[i - 1]) + d[i - 1], abs(a[i] - a[i - 2]) + d[i - 2]);
    }
    cout << d[n];
}

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

int main(){
    int n ;
    cin >> n ;
    int nax = 1e9 ;
    for(int i=0;i<n;i++){
        int x ;
        cin >> x ;
        int cnt = 0 ;
        while(x%2==0){
            cnt++ ;
            x/=2;
        }
        nax = min(nax,cnt);
    }
    cout << nax << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
#include <bitset>
#define ll long long
using namespace std;


int main() {
	int n, m, k[20], s[20][20], p[20], ans = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> k[i];
		for (int j = 0; j < k[i]; j++) {
			cin >> s[i][j];
		}
	}
	for (int i = 0; i < m; i++)cin >> p[i];
	
	int check[20];
	for (int i = 0; i < m; i++) {
		check[i] = 0;
		for (int j = 0; j < k[i]; j++) {
			check[i] |= (1 << s[i][j] - 1);
		}
	}
	int hoge, count = 0;
	for (int bit = 0; bit < (1 << n); bit++)
	{
		count = 0;
		for (int i = 0; i < m; i++) {
			hoge = __builtin_popcount(check[i] & bit);
			if (hoge % 2 == p[i])count++;
		}
		if (count == m)ans++;
	}
	cout << ans << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-9;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int cnt[1252521];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int n;
  cin>>n;
  FOR(x, 1, 101){
    FOR(y, 1, 101){
      FOR(z, 1, 101){
        ++cnt[x*x+y*y+z*z+x*y+y*z+z*x];
      }
    }
  }
  FOR(i, 1, n+1){
    cout<<cnt[i]<<'\n';
  }
  return 0;
}


Measured memory_bytes: 3868
N,K=map(int,input().split())
S=input()

X=[]
now=1
tmp=0
for i in range(N):
	if int(S[i])-0==now:
		tmp+=1
	else:
		now=1-now
		X.append(tmp)
		tmp=1
if tmp!=0:
	X.append(tmp)

n=len(X)
R=[0]*(n+1)
for i in range(n):
	R[i+1]=X[i]+R[i]

add=2*K+1
ans=0
for i in range(0,n+1,2):
	left=i
	right=min(i+add,n)
	ans=max(ans,R[right]-R[left])
print(ans)

Measured memory_bytes: 7884
import java.util.*;
import java.lang.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		System.out.println(a + " " + b + " " + (- a - b + 3 * c));
		System.out.println((-2 * a - b + 4 * c) + " " + c + " " +  (2 * a + b - 2 * c));
		System.out.println((a + b - c) + " " + (- b + 2 * c) + " " + (- a + 2 * c));
	}
}

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

int main(void){
    string s; cin >> s;
    for(int i=0; i<3; i++){
        if(s[i]=='9') s[i]='1';
        else if(s[i]=='1') s[i]='9';
    }

    cout << s << endl;
    
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
int main(void){

  int A, B;
  int n = 0;
  int i;

  scanf("%d %d", &A, &B);

  char S[16];

  scanf("%s", S);

  for(i = 0; i < A; i++){
    if(S[i] == '-'){
      break;
    }else{
      n++;
    }
  }
  if(S[A] == '-'){
    n++;
  }
  for(i = A + 1; i < A + B + 1; i++){
    if(S[i] == '-'){
      break;
    }else{
      n++;
    }
  }

  if(n == A + B + 1){
    printf("Yes\n");
  }else{
    printf("No\n");
  }

  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<functional>
#include<queue>

#define INFTY 1<<30
#define N 101
#define C 11
#define CONNECTED 1
#define IN_QUEUE 1

using namespace std;

int cost[N][C];
bool vis[N][C];
int W[N][N];
int G[N][N];

class Node{
public:
	Node():id(0),cost(INFTY),c(0){}
	int id;
	int cost;
	int c;
	bool operator>(const Node &t)const{return this->cost > t.cost;}
};

void Dijkstra( Node s ){
	priority_queue< Node,vector<Node>,greater<Node> > pq;

	pq.push( s );

	while( !pq.empty() ){
		Node p = pq.top();

		pq.pop();

		if( vis[p.id][p.c] )
			continue;
		vis[p.id][p.c] = true;
		cost[p.id][p.c] = min( cost[p.id][p.c], p.cost );

		for(int i = 0; i < N; ++i){
			if( G[p.id][i] == CONNECTED ){
				Node np;

				np.id = i;
				np.cost = cost[p.id][p.c] + W[p.id][i];
				np.c = p.c;
				pq.push( np );
				if( p.c > 0 ){
					np.cost = cost[p.id][p.c] + (W[p.id][i]/2);
					np.c = p.c - 1;
					pq.push( np );
				}
			}
		}
	}
}
void ResetGraph(){
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < C; ++j){
			cost[i][j] = INFTY;
			vis[i][j] = false;
		}
		for(int j = 0; j < N; ++j){
			G[i][j] = 0;
			W[i][j] = 0;
		}
	}
}
int main(){
	while( true ){
		int c, n, m, s, d;
		int ans = INFTY;
		Node start;
		
		cin >> c >> n >> m >> s >> d;
		if( !(c||n||m||s||d) )
			break;

		ResetGraph();
		for(int i = 0; i < m; ++i){
			int a, b, f;

			cin >> a >> b >> f;
			G[a][b] = G[b][a] = CONNECTED;
			W[a][b] = W[b][a] = f;
		}
		start.id = s;
		start.cost = 0;
		start.c = c;

		Dijkstra( start );

		for(int i = 0; i < C; ++i){
			ans = min(ans, cost[d][i]);
		}
		cout << ans << '\n';
	}
	return 0;
}

Measured memory_bytes: 1116
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int n;
    cin >> n;
    auto as=vector<int>(n+2);
    as[0]=as[n+1]=0;
    for(int i=0; i<n; ++i){
        cin >> as[i+1];
    }
    int cost=0;
    for(int i=1; i<n+2; ++i){
        cost+=abs(as[i]-as[i-1]);
    }
    for(int i=1; i<n+1; ++i){
        int res;
        if(as[i-1] <= as[i] && as[i] <= as[i+1]) res=cost;
        else res=cost-(abs(as[i]-as[i-1])+abs(as[i+1]-as[i]))+abs(as[i+1]-as[i-1]);
        cout << res << "\n";
    }
    return 0;
}


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

S = input()

ans = 'Yes'
for i in range(len(S)//2):
  if S[i] != S[len(S)-1-i]:
    ans = 'No'

front = S[0:(len(S)-1)//2]
for i in range(len(front)//2):
  if front[i] != front[len(front)-1-i]:
    ans = 'No'

end = S[(len(S)+1)//2:]
for i in range(len(end)//2):
  if end[i] != front[len(end)-1-i]:
    ans = 'No'
print(ans)

Measured memory_bytes: 61944
import java.util.Arrays;
import java.util.Scanner;

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

		long[] abc = new long[3];
		for (int i = 0; i < abc.length; i++) {
			abc[i] = sc.nextInt();

			if (abc[i] % 2 == 0) {
				System.out.println("0");
				return;
			}
		}

		Arrays.sort(abc);

		long ans = abc[0] * abc[1];
		System.out.println(ans);

		sc.close();
	}

}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

vector<int> A;
vector<int> B;

int main(){
    int N;
    int saves;
    cin >> N;
    A.resize(N);
    rep(i,N) cin >> A[i];
    reverse(A.begin(), A.end());

    B.push_back(A[0]);
    for(int i=1; i<N; i++){
        auto insrt = upper_bound(B.begin(), B.end(), A[i]);
        auto tmp = insrt-B.begin();
        //cout << tmp << endl;
        if(tmp==B.size()){
            B.push_back(A[i]);
        }else{
            B[tmp] = A[i];
        }
    }
    cout << B.size() << endl;
    return 0;
}

Measured memory_bytes: 1276
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <functional>
#include <map>
#include <set>
#include <cmath>
using namespace std;
 
#define INT_MAX 2147483647
 

// DP !!
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);

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

    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    dp[1] = abs(a[1] - a[0]);
    for (int i = 2; i < n; i++) {
        for (int j = 1; j <= min(k, i); j++) {
            dp[i] = min(dp[i], dp[i - j] + abs(a[i] - a[i - j]));
        }
    }
        

    cout << dp[n - 1] << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a,b,c,d;
int main()
{
	scanf("%d%d%d%d",&a,&b,&c,&d);
	printf("%d\n",max(a*b,c*d));
	return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextLong()

    println(calc(n))
}

fun calc(n: Long): Long {
    var cnt = 0L
    (1L..n).forEach { a ->
        (1..n / a).forEach { b ->
            val c = n - (a*b)
            if (a * b + c == n && c > 0) cnt++
        }
    }
    return cnt
}

Measured memory_bytes: 53284
# coding: utf-8

s = raw_input()

def isp(x):
    leng = len(x)
    #print leng
    #print [(s[i], s[leng - i - 1]) for i in xrange(leng // 2)]
    return all(s[i] == s[leng - i - 1] for i in xrange(leng // 2))

n = len(s)
x1 = s[0:n // 2]
x2 = s[(n + 3) // 2 - 1:n]
#print s
#print x1,0,n//2
#print x2,(n+3)//2-1,n
print ['No', 'Yes'][isp(s) and isp(x1) and isp(x2)]


Measured memory_bytes: 2568
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
struct edge{
    int to,cost;
    edge(int a,int b):to(a),cost(b){}
    edge(){}
    bool operator>(const edge &d)const{
        return cost>d.cost;
    }
};
int main(){
    int N;
    while(scanf("%d",&N),N){
        int M;
        scanf("%d",&M);
        vector<vector<edge> >V(N);
        for(int i=0;i<M;i++){
            int a,b,c;
            scanf("%d,%d,%d",&a,&b,&c);
            c=c/100-1;
            V[a].push_back(edge(b,c));
            V[b].push_back(edge(a,c));
        }

        bool used[100];fill(used,used+100,false);
        int res=0;
        priority_queue<edge,vector<edge>,greater<edge> >Q;
        Q.push(edge(0,0));
        while(Q.size()){
            int to=Q.top().to,cost=Q.top().cost;
            Q.pop();
            if(used[to])continue;
            used[to]=true;
            res+=cost;
            for(int i=0;i<V[to].size();i++)Q.push(V[to][i]);
        }
        printf("%d\n",res);
    }
    return 0;
}

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


void solve(long long N, long long A, long long B){
    if(N*A <= B) cout << N*A << endl;
    else cout << B << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(N, A, B);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	//input
	int64_t N;
	string S;
	cin >> N >> S;

	//calculation
	int64_t r = 0;
	int64_t g = 0;
	int64_t b = 0;
	for (int64_t i = 0; i < N; i++) {
		if (S[i] == 'R') {
			r++;
		} else if (S[i] == 'G') {
			g++;
		} else {
			b++;
		}
	}

	int64_t output = r * g * b;
	for (int64_t i = 0; i < N - 2; i++) {
		for (int64_t j = i + 1; j < N - 1; j++) {
			int64_t k = 2 * j - i;
			if (k >= N) {
				continue;
			}
			if (S[i] != S[j] && S[i] != S[k] && S[j] != S[k]) {
				output--;
			}
		}
	}


	//output
	cout << output << endl;


	return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool check_edge(vector<int> vv, int i, vector<int> e) {
    if(min(vv[i], vv[i+1])==e[0] && max(vv[i], vv[i+1])==e[1]) return true;
    else return false;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int> > edge(M, vector<int>(2));
    for(int i=0; i<M; i++) {
        for(int j=0; j<2; j++) {
            cin >> edge[i][j];
        }
    }
    
    vector<int> v(N);
    
    for(int i=0; i<N; i++) {
        v[i] = i+1;
    }

    int ans=0;
    bool flag;

    do {
        if(v[0]!=1) continue;
        for(int j=0; j<N-1; j++) {
            flag=false;
            for(int k=0; k<M; k++) {
                if(check_edge(v, j, edge[k])) {
                    flag=true;
                    break;
                }
            }
            if(flag) continue;
            else break;
        }
        
        if(flag) ans++;

        // for(int i=0; i<N; i++) {
        //     cout << v[i] << " ";
        // }
        // cout << endl;

        
        
    } while(next_permutation(v.begin(), v.end()));

    cout << ans << endl;

    return 0;
    
}

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

const int N = 50;

pair<double,double> dat[N+5];

int main() {
    pair<double,double> summ = make_pair((double)0.0, (double)0.0);

    int n; scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%lf %lf", &dat[i].first, &dat[i].second);
        summ.first += dat[i].first;
        summ.second += dat[i].second;
    }
    summ.first /= (double)n;
    summ.second /= (double)n;

    double res = (double)0.0;
    double P = (double)1.0;

    for (int xxx=0; xxx<300000; xxx++) {
        int f = 1;
        res = hypot(summ.first - dat[1].first, summ.second - dat[1].second);

        for (int i=1; i<=n; i++) {
            double ret = hypot(summ.first - dat[i].first, summ.second - dat[i].second);
            if (res < ret) res = ret, f = i;
        }

        summ.first += (dat[f].first - summ.first)*P;
        summ.second += (dat[f].second - summ.second)*P;
        P *= 0.999;
    }

    printf("%.8lf\n", res);
    return 0;
}


Measured memory_bytes: 384
package main

import (
	"fmt"
	"math"
)

func dist(y, z []int) int {
	d := 0
	for i := 0; i < len(y); i++ {
		d += (y[i] - z[i]) * (y[i] - z[i])
	}
	return d
}

func round(f float64) float64 {
	return math.Floor(f + .5)
}

func main() {
	var n, d int
	fmt.Scan(&n, &d)
	x := make([][]int, n)
	for i := 0; i < n; i++ {
		x[i] = make([]int,d)
		for j := 0 ;j<d;j++ {
			fmt.Scan(&x[i][j])
		}
	}
	var count, distance int
	var fDistance float64
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if i < j {
				distance = dist(x[i], x[j])
				fDistance = float64(distance)
				if int(round(math.Pow(fDistance, 0.5))*round(math.Pow(fDistance, 0.5))) == distance {
					count++
				}
			}
		}
	}
	fmt.Println(count)
}

Measured memory_bytes: 512
while 1:
	H, W = map(int, raw_input().split())
	if H == W == 0:
		break
	for h in range(H):
		if h % 2 == 0:
			if W % 2 == 0:
				print ("#."*(W//2))
			else:
				print ("#."*(W//2) + "#")
		else:
			if W % 2 == 0:
				print (".#"*(W//2))
			else:
				print (".#"*(W//2) + ".")
	print ""

Measured memory_bytes: 6388
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
  int N, X, Y;
  cin >> N >> X >> Y;
  X--;
  Y--;
  map<int, int> ans;
  for(int i = 0; i < N; i++){
    for(int j = i + 1; j < N; j++){
      if(i <= X && j >= Y)
        ans[j - i - (Y - X)]++; 
      else{
        int itr = j - i - 1;
        itr = min(itr, abs(i - X) + abs(Y - j));
        ans[itr]++;
      }
    }
  }
  rep(i, N - 1){
    cout << ans[i] << endl;
  }
  
}

Measured memory_bytes: 384
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

#[allow(dead_code)]
struct Scanner<'a> {
    cin: StdinLock<'a>,
}
#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn input<T: FromStr>(&mut self) -> T {
        self.read().unwrap()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let (n, a, b): (isize, isize, isize) = (sc.input(), sc.input(), sc.input());

    let mut ans = 0;
    for i in 1..n + 1 {
        let sum = digit_sum(i);
        if sum >= a && sum <= b { ans += i; }
    }
    println!("{}", ans);
}

fn digit_sum(n: isize) -> isize {
    let mut res = 0;

    let mut x = n;
    while x > 0 {
        res += x % 10;
        x /= 10;
    }
    res
}


Measured memory_bytes: 4352
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int n;
  while(cin>>n){
    if(n==0) break;
    vector<int> ary;
    int tmp;
    REP(i,n){
      cin>>tmp;
      ary.push_back(tmp);
    }
    int countt = 0;
    while(true){
      vector<int> ary2;
      REP(i,n){
        ary2.push_back(count(ary.begin(),ary.end(),ary[i]));
      }
      if(ary==ary2){
        cout<<countt<<endl;
        bool f = false;
        REP(i,n){
          if(f) cout<<" ";
          f = true;
          cout<<ary[i];
        }
        cout<<endl;
        break;
      }
      ary = ary2;
      countt++;
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
int main(){
	int N;scanf("%d",&N);
	for(int i=0;i<N;i++){
		int t;scanf("%d",&t);
		if(t%2==0&&(t%3!=0&&t%5!=0)){
			printf("DENIED");
			return 0;
		}
	}
	printf("APPROVED");
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#pragma warning(disable : 4996)
using namespace std;
int n, c, p[500009], ip[500009], v[500009], bit[500009], inv[500009], mod = 1000000007;
void add(int pos, int val) {
	for (int i = pos + 1; i <= n; i += i & (-i)) bit[i] += val;
}
int sum(int pos) {
	int ret = 0;
	for (int i = pos; i >= 1; i -= i & (-i)) ret += bit[i];
	return ret;
}
int main() {
	scanf("%d", &n);
	inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = 1LL * inv[mod % i] * (mod - mod / i) % mod;
	for (int i = 0; i < n; i++) ip[i] = -1;
	for (int i = n - 1; i >= 0; i--) {
		scanf("%d", &p[i]), p[i]--;
		if(p[i] != -1) ip[p[i]] = i;
	}
	int f1 = 1;
	for (int i = 0; i < n; i++) {
		if (ip[i] == -1) {
			v[c++] = i;
			f1 = 1LL * f1 * c % mod;
		}
	}
	int ret = 0, fact = 1, cur = 0, cs = 0;
	for (int i = 0; i < n; i++) {
		if (p[i] != -1) {
			ret = (ret + 1LL * fact * sum(p[i]) % mod * f1) % mod;
			ret = (ret + 1LL * fact * (lower_bound(v, v + c, p[i]) - v) % mod * f1 % mod * inv[c] % mod * cur) % mod;
			cs += c - (lower_bound(v, v + c, p[i]) - v);
			if (cs >= mod) cs -= mod;
			add(p[i], 1);
		}
		else {
			ret = (ret + 1LL * fact * cs % mod * f1 % mod * inv[c]) % mod;
			ret = (ret + 1LL * fact * cur % mod * f1 % mod * inv[2]) % mod;
			cur++;
		}
		fact = 1LL * fact * (i + 1) % mod;
	}
	printf("%d\n", (ret + f1) % mod);
	return 0;
}

Measured memory_bytes: 9984
#include<iostream>
#include<algorithm>
using namespace std;
const int N=12;
int ar[N];
int main(){
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
	}
	sort(ar+1,ar+1+n);
	j=0;
	for(i=1;i<n;i++){
		j+=ar[i];
	}
	if(j>ar[n]){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
}

Measured memory_bytes: 256
from sys import stdin


def main():
    input()
    readline = stdin.readline
    A = tuple(map(int, readline().split()))
    B = tuple(map(int, readline().split()))
    pre = A[0]
    ans = 0
    for a, b in zip(A[1:], B):
        tmp1 = pre if pre < b else b
        b -= tmp1
        tmp2 = a if a < b else b
        ans += tmp1 + tmp2
        pre = a - tmp2
    print(ans)
    return


main()


Measured memory_bytes: 18624
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define SZ(x) ((int)(x.size()))
#define FOR(i,s,n) for (ll i = (s); (i) < (n); ++i)
#define FORD(i,s,l) for (ll i = (s); (i) >= l; --i)
#define F first
#define S second
#define TC int __tc; cin >> __tc; FOR(case_num,1,__tc+1)
#define TEST(x,i) ((x)&(1ll<<(i)))
#define SET(x,i) ((x)|(1ll<<(i)))
#define FLIP(x,i) ((x)^(1ll<<(i)))
#define CLEAR(x,i) ((x)&~(1ll<<(i)))

const double pi = 4 * atan(1);
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;
const int MAXN = 200005;

ll ceilDiv(ll a, ll b) {
	return a / b + (a % b != 0);
}

ll a[5];

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

	ll n;
	cin >> n;

	
	FOR(i,0,5)
	{
		cin >> a[i];
	}

	ll low = a[0];
	FOR(i,0,5) {
		low = min(low,a[i]);
	}

	cout << 5+(ceilDiv(n,low)-1) << "\n";
}


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



int main()
{
	string s,t;
	cin>>s>>t;
	for(int i=0;i<t.length();i++)
	{
		cout<<s[i]<<t[i];
	}
	if(s.length()>t.length())cout<<s[s.length()-1];
	cout<<endl;	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <inttypes.h>
#include <stdint.h>

#define __STDC_FORMAT_MACROS

int main(void)
{
	int32_t knownCats, unknown, sumCats;

	scanf("%I32d %I32d %I32d", &knownCats, &unknown, &sumCats);

	printf("%s", ((knownCats <= sumCats) && (sumCats <= knownCats + unknown)) ? "YES" : "NO");

	return 0;
}


Measured memory_bytes: 128
N = int(input())
H = list(map(int,input().split()))

for i in range(1,N):
    ind = N - i - 1
    if H[ind+1] == H[ind] - 1:
        H[ind] -= 1
    elif H[ind+1] < H[ind] - 1:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 14396
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    int x,y,z;
    cin>>x>>y>>z;
    swap(x,y);
    swap(x,z);
    cout<<x<<" "<<y<<" "<<z;







}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI acos(-1.0)
#define test() int t; cin>>t; while(t--)
#define ll long long int
int mod = 1e9 + 7;
int main()
{
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n;
	cin >> n;
	string ans = "";
	while (n--) {
		ans += ('a' + n % 26);
		n /= 26;
	}
	reverse(ans.begin(), ans.end());
	cout << ans;
	return 0;
}


Measured memory_bytes: 3660
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll k,q;cin>>k>>q;
  V<ll> d(k);
  rep(i,0,k){
    cin>>d[i];
  }

  while(q--){
    ll n,x,m;cin>>n>>x>>m;  
    ll st=0,last=x%m;
    rep(i,0,k){
      if(d[i]%m){
        ll cnt=(n-1)/k + (i<(n-1)%k);
        st+=cnt;
        last+=cnt*(d[i]%m);
      }
    }
    cout<<st-(last/m)<<ENDL;
  }
}
//( ・ __ ・ ) KEEP BEING ORGANIZED
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 384
using System;

public class Program
{
    public static long loop;

    static char[] sc;

    static string output;

    public static void Main(string[] args)
    {
        loop = 0;

        Input();
        Proc();
        Output();
    }

    static void Input()
    {
        //string[] input = null;

        // 文字列を数値の配列として読込
        sc = Console.ReadLine().ToCharArray();
    }

    static void Proc()
    {
        for (char c = 'a'; c <= 'z'; c++)
        {
            for (long idx = 0; idx < sc.Length - 1; idx++)
            {
                // 2文字のパターン
                if (sc[idx] == sc[idx + 1])
                {
                    output = string.Format("{0} {1}", idx + 1, idx + 2);
                    return;
                }

                // 3文字のパターン
                if (idx < sc.Length - 2 && sc[idx] == sc[idx + 2])
                {
                    output = string.Format("{0} {1}", idx + 1, idx + 3);
                    return;
                }
            }
        }

        output = string.Format("{0} {1}", -1, -1);
    }

    static void Output()
    {
        // 出力
        Console.WriteLine(output);
        output = string.Empty;
    }
}


Measured memory_bytes: 13780
/**
 *      purpose : 
 *      author  : kyomukyomupurin
 *      created : 
**/

// input/output
#include <iostream>
#include <fstream>
#include <sstream>
// container class
#include <array>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// math, algorithm
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
// etc
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstring>
#include <chrono>
#include <iomanip>
#include <random>
#include <utility>
// using-directive
using namespace std;
// alias template
using int64 = long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;
// text macro replacement
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define print(x) cout << (x) << '\n'
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// variadic template
template<typename T> inline void chmin(T &a, T b) {if (a > b) a = b; return;}
template<typename T> inline void chmax(T &a, T b) {if (a < b) a = b; return;}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;
const int MOD = 1000000007;

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

  int a, b; cin >> a >> b;
  cout << max({a + b, a - b, a * b}) << endl;

  return 0;
}

Measured memory_bytes: 892
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
AC
ある要素をA,B,C,使わないのどれにするか
解説と同じ実装にした
*/

ll n,x[3],l[10];

ll dfs(ll a,ll b,ll c,ll t){
	if(t==n){
		if(min({a,b,c})>0){
			return abs(a-x[0])+abs(b-x[1])+abs(c-x[2])-30;
		}else{
			return 1e18;
		}
	}
	ll ans=1e18;
	ans=min(ans,dfs(a,b,c,t+1));
	ans=min(ans,dfs(a+l[t],b,c,t+1)+10);
	ans=min(ans,dfs(a,b+l[t],c,t+1)+10);
	ans=min(ans,dfs(a,b,c+l[t],t+1)+10);
	return ans;
}

int main(void){
	cin>>n;
	rep(i,3)cin>>x[i];
	rep(i,n)cin>>l[i];
	// cout<<((1<<n)-1)<<endl;
	cout<<dfs(0,0,0,0)<<endl;
	return 0;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  vl w(n);
  ll sum = 0;
  REP(i,n){
    cin >> w[i];
    sum += w[i];
  }
  ll ans = 1e9;
  ll tmp = 0;
  REP(i,n-1){
    tmp += w[i];
    CHMIN(ans,abs(sum-2*tmp));
  }
  cout << ans<< endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a;
    cin>>a;
    int cnt=0;  
    for(int i=0;i<a.size();i++)
    {
        if(a[i]=='C') cnt=1;
        if(a[i]=='F'&&cnt==1)
        {
            cout<<"Yes";
            return 0;
        }
    }
    cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(x) (int)(x).size()
#define endl '\n'
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
#define CEIL(a, b) ((a) + (b)-1) / (b)
template <class T>
bool ckmin(T& a, const T& b) {
  return a > b ? a = b, true : false;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, true : false;
}
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout \
  if (DEBUG) std::cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << mt(__VA_ARGS__) << "] "
template <typename T>
struct IsC {
  template <typename C>
  static char test(typename C::const_iterator*);
  template <typename C>
  static int test(...);
  static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
  static const bool value = false;
};
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream&, const C&);
template <typename T1, typename T2>
ostream& operator<<(ostream&, const pair<T1, T2>&);
template <typename... T> using TS = tuple_size<tuple<T...>>;
template<size_t idx, typename... T>
typename enable_if<TS<T...>::value == idx + 1, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return o << ", " << get<idx>(t) << ')';
}
template<size_t idx, typename... T>
typename enable_if<0 < idx && idx + 1 < TS<T...>::value, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << ", " << get<idx>(t), t);
}
template<size_t idx = 0, typename... T>
typename enable_if<1 < TS<T...>::value && !idx, ostream&>::type
operator<<(ostream& o, const tuple<T...>& t) {
  return operator<<<idx + 1>(o << '(' << get<idx>(t), t);
}
template<typename T>
ostream& operator<<(ostream& o, const tuple<T>& t) {
  return o << get<0>(t);
}
template <typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p) {
  return o << mt(p.fi, p.se);
}
template <typename C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(
    ostream& o, const C& c) {
  o << '[';
  for (auto it = c.cbegin(); it != c.cend(); ++it)
    o << *it << (next(it) != c.cend() ? ", " : "");
  return o << ']';
}
template <typename T>
void tprint(vector<vector<T>>& v, size_t width = 0, ostream& o = cerr) {
  if (!DEBUG) return;
  for (auto& vv : v) {
    for (auto& i : vv) o << setw(width) << i;
    o << endl;
  }
}

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

  int l, r, d; cin >> l >> r >> d;
  cout << r / d - (l + d - 1) / d + 1 << endl;
  
  return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <deque>
#define pb push_back
#define mod 1000000007
#define all(x) x.begin(),x.end()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;

int main(void){
  int n,m,k;
  cin>>n>>m>>k;
  if((k%m==0)||(k%n==0)){
    cout<<"Yes"<<endl;
    return 0;
  }
  int t;
  if(n<m){t=m;  m=n;  n=t;}
  for(int i=1;i<n;i++){
    int t1,t2;
    t1=i;t2=n-i;
    for(int j=1;j<m;j++){
      if(k==t1*j + t2*(m-j)){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
a = list(map(int,input().split()))

if 0 <= a[2] + a[4] <= a[0] and 0 <= a[3] + a[4] <= a[1] and \
    0 <= a[2] - a[4] <= a[0] and 0 <= a[3] - a[4] <= a[1]:
    print('Yes')

else:
    print('No')


Measured memory_bytes: 5596
N = int(input())
a = 0
b = 0
ans = 0
s = 10000
for i in range(1,int(N/2) + 1):
    a = i
    b = N - i
    ans = 0
    while 1:
        ans += a % 10 + b % 10
        a = a // 10
        b = b // 10
        if a == 0 and b == 0:
            if ans < s:
                s = ans
            break
print(s)


Measured memory_bytes: 9020