akhauriyash/Code-Regression huggingface dataset:
// siquareさんのを参考
// http://siquare.hatenablog.com/entry/2012/04/21/121224
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

inline ll lcm(ll a, ll b)
{
    return a / __gcd(a, b) * b;
}

int main()
{
    int n;

    while (cin >> n, n) {
        ll d[n], v[n];

        for (int i = 0; i < n; ++i) {
            cin >> d[i] >> v[i];
            int gd = __gcd(d[i], v[i]);
            d[i] /= gd;
            v[i] /= gd;
        }

        ll gv = __gcd(v[0], v[1]), ld = lcm(d[0], d[1]);
        for (int i = 2; i < n; ++i) {
            gv = __gcd(gv, v[i]);
            ld = lcm(ld, d[i]);
        }

        for (int i = 0; i < n; ++i)
            cout << ld * v[i] / gv / d[i] << endl;
    }

    return 0;
}

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

int main() {
  string sd, t;
  cin >> sd >> t;

  string s = sd;
  bool res = false;
  for (int i = sd.size() - 1; i >= 0; i--) {
    int cnt  = 0;
    string a = s;
    for (int j = 0; j < t.size(); j++) {
      int index = i - t.size() + 1 + j;
      if (index >= sd.size()) break;
      if (sd[index] == t[j] || sd[index] == '?') {
        cnt++;
        a[index] = t[j];
      } else {
        break;
      }
    }
    if (cnt == t.size()) {
      s   = a;
      res = true;
      // i -= (t.size() - 1);
      break;
    }
  }
  if (!res) {
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '?') {
      cout << 'a';
    } else {
      cout << s[i];
    }
  }
  cout << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>

#define _GLIBCXX_DEBAC
using namespace std;


int main() {
	string s;
	cin >> s;
	if (s == "SUN") {
		cout << 7;
	}else if(s == "MON") {
		cout << 6;
	}
	else if (s == "TUE") {
		cout << 5;
	}
	else if (s == "WED") {
		cout << 4;
	}
	else if (s=="THU") {
		cout << 3;
	}
	else if (s=="FRI") {
		cout << 2;
	}
	else {
		cout << 1;
	}
		return 0;
}









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

using namespace std;
typedef long long ll;

int main()
{
    ll x, answer = 0;
    ll current = 100;
    cin >> x;

    while (current < x) {
        current = floor(current * 1.01);
        answer++;
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 3712
n=int(input())
stotal = 0
smin = 100
i = 0
while i < n:
    s0 = int(input())
    stotal += s0
    if s0%10 != 0 and s0 < smin:
        smin = s0
    i += 1
if stotal%10 != 0:
    print(stotal)
else:
    if smin == 100:
        print(0)
    else:
        print(stotal-smin)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0 ; i < n ; i++) {
            s[i] = sc.next();
        }
        String ans = "";
        for (char c = 'a' ; c <= 'z' ; c++) {
            int x = 50;
            for (int i = 0 ; i < n ; i++) {
                int count = 0;
                for (int j = 0 ; j < s[i].length() ; j++) {
                    if (c == s[i].charAt(j)) {
                        count++;
                    }
                }
                x = Math.min(x,  count);
            }
            for (int i = 0 ; i < x ; i++) {
                ans += String.valueOf(c);
            }
        }
        System.out.println(ans);

    }

}


Measured memory_bytes: 22868
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template<class F>auto recursive(F f){return[f](auto...a){return f(f,a...);};}
template<class I,class V=typename I::value_type>V sum_up(const I&l,const I&r){V v;for(I i=l;i!=r;i++)v=i==l?*i:v+*i;return v;}
template<class I,class T=iterator_traits<I>>I operator+(I it,int n){for(int i=0;i<n;i++)it++;return it;}
template<class I,class T=iterator_traits<I>>I operator-(I it,int n){for(int i=0;i<n;i++)it--;return it;}
template<class T>using rev_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using vector2d=vector<vector<T>>;
struct fixprec{int p;fixprec(int p):p(p){}};
ostream&operator<<(ostream&o,fixprec f){return o<<fixed<<setprecision(f.p);}
void R_YESNO(bool p){cout<<(p?"YES":"NO")<<endl;}
void R_YesNo(bool p){cout<<(p?"Yes":"No")<<endl;}
int main() {
    int N;
    cin >> N;
    set<string> s;
    for(int i = 0; i < N; i++) {
        string S;
        cin >> S;
        s.insert(S);
    }
    cout << s.size() << endl;
    return 0;
}


Measured memory_bytes: 19252
#include <iostream>
#include <set>
#include <vector>

using namespace std;

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

    set<string> S;

    for (long _ = 0; _ < n; _++)
    {
        string op, arg;
        cin >> op >> arg;

        if (op == "insert")
        {
            S.insert(arg);
        }
        else
        {
            if (S.find(arg) == S.end())
            {
                cout << "no" << endl;
            }
            else
            {
                cout << "yes" << endl;
            }
        }
    }
}



Measured memory_bytes: 32188
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N, K;
	in >> N >> K;
	std::vector<LL>h(N);
	rep(i, N) in >> h[i];

	std::sort(h.begin(), h.end());

	LL ans = 1145148101919;
	rep(i, N - K + 1)
	{
		LL min = h[i], max = h[i + K - 1];
		ans = std::min(ans, max - min);
	}

	out << ans << std::endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

template<typename T>
struct Matrix {
    Matrix(int r, int c) : _r(r), _c(c), a(r * c) {}
    T* operator[](int r) { return r * _c + a.data(); }
    int _r, _c;
    vector<T> a;
};

struct lcs_solver {
    int f(int i, int j)
    {
        if (i < 0 || j < 0) return 0;
        return lcs[i][j];
    }
    lcs_solver(const string& s, const string& t) : s(s), t(t), lcs(s.size(), t.size())
    {
        int n = s.size(), m = t.size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                lcs[i][j] = max({f(i - 1, j), f(i, j - 1), f(i - 1, j - 1) + (s[i] == t[j])});
    }
    string trace() { return trace((int) s.size() - 1, (int) t.size() - 1); }
    string trace(int i, int j)
    {
        if (i < 0 || j < 0) return {};
        if (s[i] == t[j] && lcs[i][j] == f(i - 1, j - 1) + 1) {
            return trace(i - 1, j - 1) += s[i];
        }
        else if (lcs[i][j] == f(i - 1, j))
            return trace(i - 1, j);
        else
            return trace(i, j - 1);
    }

    string s, t;
    Matrix<int> lcs;
};

int main()
{
    string s, t;
    cin >> s >> t;
    cout << lcs_solver(s, t).trace();
    return 0;
}


Measured memory_bytes: 35840
/*
 * Problem Description: Elementary Number Theory - Power
 * Category:
 * Author: Khan
 * Date: 16th October, 2017
 */

#include <iostream>
#include <cstdlib>
#include <cmath>

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

ull mod_pow(ull x, ull n, ull mod)
{
    ull res = 1;
    while(n > 0)
    {
        if(n & 1)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int main(int argc, char const *argv[])
{
    //freopen("sample.txt", "r", stdin);
    ull m, n;
    cin >> m >> n;
    cout << mod_pow(m, n, 1e9 + 7) << endl;
    return 0;
}

Measured memory_bytes: 3092
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%s", $s);

if ($n % 2 == 0){
  $len = $n / 2;
  $ans = '';
  $a = substr($s, 0, $len);
  $b = substr($s, $len);
  if ($a == $b){
    echo 'Yes';
  }else{
    echo 'No';
  }
}else{
  echo 'No';
}

?>

Measured memory_bytes: 3576
#include <stdio.h>
#include <math.h>
int main(void) {
	int i;
	double positions[1001][2], x, y, rad;

	positions[1][0] = 1.0;
	positions[1][1] = 0.0;
	for (i = 2; i < 1001; i++) {
		x = positions[i-1][0];
		y = positions[i-1][1];
		rad = atan2(y, x) + M_PI_2;
		positions[i][0] = x + cos(rad);
		positions[i][1] = y + sin(rad);
	}

	while (1) {
		scanf("%d ", &i);
		if (i == -1)
			break;

		printf("%0.2lf\n%0.2lf\n", positions[i][0], positions[i][1]);
	}
	return 0;
}

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

int main()
{
	int N;
	int A[100000];
	int B[100000];

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}

	for (int i = 0; i < N; i++)
	{
		B[A[i]-1] = i+1;
	}

	for (int i = 0; i < N; i++)
		printf("%d ", B[i]);


	return 0;
}
	

Measured memory_bytes: 1536
#include <stdio.h>

int rot[24][7] = {
   { 0,1,2,3,4,5,6 },{ 0,1,3,5,2,4,6 },{ 0,1,4,2,5,3,6 },{ 0,1,5,4,3,2,6 },
   { 0,2,6,3,4,1,5 },{ 0,2,3,1,6,4,5 },{ 0,2,1,4,3,6,5 },{ 0,2,4,6,1,3,5 },
   { 0,3,1,2,5,6,4 },{ 0,3,2,6,1,5,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
   { 0,4,1,5,2,6,3 },{ 0,4,2,1,6,5,3 },{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },
   { 0,5,1,3,4,6,2 },{ 0,5,3,6,1,4,2 },{ 0,5,4,1,6,3,2 },{ 0,5,6,4,3,1,2 },
   { 0,6,2,4,3,5,1 },{ 0,6,3,2,5,4,1 },{ 0,6,5,3,4,2,1 },{ 0,6,4,5,2,3,1 } };
int assign[7];

int main()
{
   int i, j;
   int a[7], b[7], dice[7];

   for (i = 1; i <= 6; i++) scanf("%d", assign+i);
   for (i = 1; i <= 6; i++) scanf("%d", a+i);
   for (j = 0; j < 24; j++) {
       for (i = 1; i <= 6; i++) dice[i] = rot[j][i];
       for (i = 1; i <= 6; i++) b[i] = assign[dice[i]];
       for (i = 1; ; i++) {
           if (i > 6) { puts("Yes"); return 0; }
           if (a[i] != b[i]) break;
       }
   }
   puts("No");
   return 0;
}


Measured memory_bytes: 2104
//stackを使うなんて全く思いつきもしませんでした、辛い
#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<algorithm>
//#include<cstring>

using namespace std;

int main(){
  string s;//断面図の文字列
  cin >> s;
  int l;//文字列の長さ
  stack<int> S;
  vector<pair<int,int>> a;//両端点
  l=s.length();
  for(int i=0;i<l;i++){
    //char型にするには''、string型にするには""
    if(s[i]=='/'){
      if(S.size()!=0){
        a.push_back(make_pair(S.top(),i));
        S.pop();
      }
    }else if(s[i]=='\\'){//エスケープシーケンス
      S.push(i);
    }
  }
  sort(a.begin(),a.end());

  /*
  for(auto i=a.begin();i<a.end();i++){
    cout << (*i).first << (*i).second << endl;
  }
  */

  auto k1= a.begin();//kにはある水たまりの両端が入っててそれを含むものがあったら上書き
  int k2=0;//k2にはその水たまりの面積が入っている
  vector<int> b;//水たまりの面積を格納したvector
  for(auto i=a.begin();i<a.end();i++){
    if((*k1).first <= (*i).first && (*i).second <= (*k1).second){
      k2+=((*i).second-(*i).first);
      //cout << k2 << endl;
    }else{
      //cout << 0 << endl;
      b.push_back(k2);
      k1=i;
      k2=((*i).second-(*i).first);
    }
    if(i==a.end()-1){
      b.push_back(k2);
    }
  }
  int sum_lake=0;
  int size_vec=0;
  for(auto i=b.begin();i<b.end();i++){
    sum_lake+=(*i);
    size_vec+=1;
  }
  cout << sum_lake << endl << size_vec;
  if(size_vec!=0){
    cout << " ";
  }else{
    cout << endl;
  }
  for(auto i=b.begin();i<b.end();i++){
    if(i==b.end()-1){
      cout << *i << endl;
    }else{
      cout << *i << " ";
    }
  }
}



Measured memory_bytes: 3280
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int dp[4010][4010], maxn;
string S, T;

int main() {
	while (cin >> S >> T) {
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < S.size(); i++) {
			for (int j = 0; j < T.size(); j++) {
				if (S[i] == T[j]) {
					dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j + 1]);
				}
			}
		}
		maxn = 0;
		for (int i = 0; i <= S.size(); i++) {
			for (int j = 0; j <= T.size(); j++) {
				maxn = max(maxn, dp[i][j]);
			}
		}
		cout << maxn << endl;
	}
}

Measured memory_bytes: 64028
#include <iostream>

using namespace std;

typedef struct _Card {
	char suit;
	int value;
} Card;

void BubbleSort(Card A[], int N) {
	for (int i = 0; i < N; i++) {
		for (int j = N - 1; j >= i + 1; j--) {
			if (A[j].value < A[j - 1].value) {
				Card t = A[j];
				A[j] = A[j - 1];
				A[j - 1] = t;
			}
		}
	}
}

void SelectionSort(Card A[], int N) {
	for (int i = 0; i < N; i++) {
		int minj = i;
		for (int j = i; j < N; j++) {
			if (A[j].value < A[minj].value) {
				minj = j;
			}
		}
		Card t = A[i];
		A[i] = A[minj];
		A[minj] = t;
	}
}

void print(Card A[], int N) {
	for (int i = 0; i < N; i++) {
		if (i > 0) cout << " ";
		cout << A[i].suit << A[i].value;
	}
	cout << endl;
}

bool isStable(Card C1[], Card C2[], int N) {
	for (int i = 0; i < N; i++) {
		if (C1[i].suit != C2[i].suit) {
			return false;
		}
	}
	return true;
}

int main() {
	Card C1[100], C2[100];
	int N;
	char ch;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C1[i].suit >> C1[i].value;
	}

	for (int i = 0; i < N; i++) {
		C2[i] = C1[i];
	}

	BubbleSort(C1, N);
	SelectionSort(C2, N);

	print(C1, N);
	cout << "Stable" << endl;
	print(C2, N);
	if (isStable(C1, C2, N)) {
		cout << "Stable" << endl;
	}
	else {
		cout << "Not stable" << endl;
	}


	return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#include<limits.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define MAX 2000000

int h = 0;
vector<int> heap(MAX); 


void maxHeapify(int i){
    int left_index = 2 * i;
    int right_index = 2 * i + 1;

    int largest_index = i;

    if(left_index <= h && heap.at(left_index) > heap.at(i)){
        largest_index = left_index;
    }
    if(right_index <= h && heap.at(right_index) > heap.at(largest_index)){
        largest_index = right_index;
    }

    if(largest_index != i){
        // インデックスiの中身とインデックスlargest_indexの中身をswap
        int tmp = heap.at(i);
        heap.at(i) = heap.at(largest_index);
        heap.at(largest_index) = tmp;
        // swapした結果、largest_indexでのヒープが崩れる可能性があるので再びheapify
        maxHeapify(largest_index);
    }

}

void buildMaxHeap(){
    for(int i = h/2; i > 0; i--){
        maxHeapify(i);
    }
}

void increaseKey(int index){
    int parent_index = index / 2;
    while(parent_index > 0 && (heap.at(index) > heap.at(parent_index))){
        int tmp = heap.at(parent_index);
        heap.at(parent_index) = heap.at(index);
        heap.at(index) = tmp;

        tmp = index;
        index = parent_index;
        parent_index = index/2;
    }
}

int main(){
    while(true){
        string command;
        cin >> command;

        if(command == "insert"){
            h++;
            int n;
            scanf("%d", &n);
            heap.at(h) = n;
            increaseKey(h);

        }else if(command == "extract"){
            cout << heap.at(1) << endl;
            heap.at(1) = heap.at(h);
            h--;
            maxHeapify(1);

        }else if(command == "end"){
            break;
        }
    }
    
    // for(int i = 1; i < h + 1; i++){
    //     cout << " " << heap.at(i);
    // }
    // cout << endl;

}


Measured memory_bytes: 10612
#include<bits/stdc++.h>
using namespace std;
const int p=1e9+7;
int s[2005],t[2005];
long long dp[2005][2005],sum[2005][2005];
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main() {
	int n=read(),m=read();
	for (int i=1; i<=n; i++) s[i]=read();
	for (int i=1; i<=m; i++) t[i]=read();
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (s[i]==t[j]) dp[i][j]=sum[i-1][j-1]+1;
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j];
			dp[i][j]%=p;
			sum[i][j]%=p;
		}
	}
	printf("%lld\n", ((sum[n][m]+1)%p+p)%p);
	return 0;
}

Measured memory_bytes: 62976
#include <stdio.h>
int main(void){    
int a, b, d, r;    
double f;    
scanf("%d %d", &a, &b);    
d = a/b;    
r = a%b;    
f = (double)a / b;    
printf("%d %d %f\n", d, r, f);    
return 0;
}


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

int dp[50];

void print() {
   for (int i = 1; i < 33; i++) {
      cout << dp[i] << " ";
   }
   cout << endl;
}

void init() {
   dp[1] = 1, dp[2] = 2, dp[3] = 4;
   for (int i = 4; i < 33; i++) {
      dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
   }
}

int main() {
   init();
   while (1) {
      int n;
      cin >> n;
      if (n == 0) break;
      int day = dp[n] / 10;
      cout << max(1, day / 365 + (day % 365 != 0)) << endl;
   }

   return 0;
}


Measured memory_bytes: 3108
#include<stdio.h>
    #define MOD 1000000007
    #define ll long long
    ll modpow(ll a,ll n,ll mod){
        ll result=1;
        while(n>0){
            if(n&1)
                result=result*a%mod;
            a=a*a%mod;
            n/=2;
        }
        return result;
    }
    ll modinv(ll a,ll mod){
        return modpow(a,mod-2,mod);
    }
    int main(){
        int n,a,b,i;
        ll ans=0,m=1,c;
        scanf("%d%d%d",&n,&a,&b);
        ans=(modpow(2,n,MOD)-1)%MOD;
        c=n;
        for(i=2;i<=a;i++){
            m=m*i%MOD;
            c=c*(n-i+1)%MOD;
        }
        ans=(ans-c*modinv(m,MOD))%MOD;
        for(;i<=b;i++){
            m=m*i%MOD;
            c=c*(n-i+1)%MOD;
        }
        ans=(ans-c*modinv(m,MOD))%MOD;
        while(ans<0){
            ans+=MOD;
        }
        printf("%lld\n",ans);
        return 0;
    }

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

int main() {
    int counta1, counta2;
    string s, a_string;

    cin >> s;

    for (int i = 0; i < s.length(); i++){
        if (s[i] == 'A'){
            counta1 = i;
            break;
        }
    }

    for (int i = s.length() - 1; i >= 0; i--){
        if (s[i] == 'Z'){
            counta2 = i;
            break;
        }
    }

    cout << counta2 - counta1 + 1 << endl;
}

Measured memory_bytes: 640
n = int(input())
a = list(map(int, input().split()))
a.insert(0, 0)
a.append(0)
summ = 0
temp = 0
for i in range(1, n + 2):
    summ += abs(a[i] - a[i-1])
for i in range(1, n + 1):
    temp = summ
    temp -= abs(a[i] - a[i-1])
    temp -= abs(a[i] - a[i+1])
    temp += abs(a[i-1] - a[i+1])
    print(temp)

Measured memory_bytes: 14048
#include <stdio.h>

int main(void) {
  /* code */
  int h, a;
  int result;
  scanf("%d %d", &h, &a );
  if(h%a==0)
    result = h/a;
  else
    result = h/a +1;
  
  printf("%d", result);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pi 3.14159265358979323846
#define mod 1000000007
ll A[200009],k,a;
ll chk(ll x)
{
    ll cnt=0;
    if(x==0) return false;
    for(ll c=0;c<a;c++)
    {
        if(A[c]>x)
        cnt=cnt+(ll)(A[c]/x);
    }
    return(cnt<=k);
}
ll binser(ll l,ll r)
{
    ll mid=((l+r)/2);
    if(l>r)
    {
        return mid;
    }
    if(chk(mid))
    {
        return min(mid,binser(l,mid-1));
    }
    else
    {
        return binser(mid+1,r);
    }
}
int main()
{
    IOS;
    ll b,c,d,e,l=0,r,ans;
    cin>>a>>k;
    for(b=0;b<a;b++) cin>>A[b];
    sort(A,A+a);
    r=A[a-1];
    ans=binser(l,r);
    cout<<ans+1<<endl;
}

Measured memory_bytes: 5148
import java.util.Scanner;

fun main (args : Array<String>) {
  val input = Scanner(System.`in`)
  
  while (input.hasNext()) {
    val N = input.nextInt()
    var target = 1;
    var breakCount = 0;
    
    for (i in 1..N) {
      val a = input.nextInt()
      
      if (a != target) {
        ++breakCount
      } else {
        ++target
      }
    }
    
    if (target == 1) {
      println(-1)
    } else {
      println(breakCount)
    }
  }
}

Measured memory_bytes: 59568
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
 

 int main(){
   ll  n , a, b , c,  d ; cin>> n>>a>>b>>c>>d ;
   ll x= abs(a-b ) ; n-- ;
    if(d*n <x ) cout<<"NO"<<endl ;
    else{
      
      bool ok= 0 ;
      rep2(i,0,n){
        ll mi = c*i- d*(n-i) ;
        ll ma = d*i-c*(n-i) ;
        if(mi<=x && x<=ma){
          ok=1 ;
        }
      }
      if(ok) cout<< "YES"<<endl ;
      else cout<< "NO"<<endl ;
      
    }

   return 0 ;
 }



Measured memory_bytes: 3592
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unordered_map>
#include <vector>

std::vector<int > a(54), b(54), c(54), d(54);
int N, M, Q;
int ans = 0;

void check(std::vector<int > input){
  int temp = 0;
  for (int i=0; i<Q; i++){
    if (input[b[i]] - input[a[i]] == c[i]){
      temp+=d[i];
    }
  }
  ans = std::max(ans, temp);
  return;
}

void dfs(std::vector<int > vec){
  if (vec.size()==N){
    check(vec);
  } else {
    int lastnum = 1;
    if (vec.size()>0){
      lastnum = vec[vec.size()-1];
    }
    for (int i=lastnum; i<=M; i++){
      std::vector<int > temp(vec.size());
      std::copy(vec.begin(), vec.end(), temp.begin());
      temp.push_back(i);
      dfs(temp);
    }
  }
  return;
}

int main(){
  scanf("%d", &N);
  scanf("%d", &M);
  scanf("%d", &Q);
  for (int i=0; i<Q; i++){
    scanf("%d", &a[i]);
    scanf("%d", &b[i]);
    scanf("%d", &c[i]);
    scanf("%d", &d[i]);
    a[i]--;
    b[i]--;
  }
  std::vector<int > vec;
  dfs(vec);
  std::cout << ans << std::endl;
  return 0;
}


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

int main(){
	int e = 0;
	int a,b,c;
	int n = 0;
	int s[20];
	int d[20][20];
	cin >> a >> b >> c;
	for(int i = 0;i<b;i++){
		cin >> s[i];
	}
	for(int i = 0;i<a;i++){
		for(int j = 0;j<b;j++){
			cin >> d[i][j];
		}
	}
	for(int i = 0;i<a;i++){
		n = 0;
		for(int j = 0;j<b;j++){
			n+=s[j]*d[i][j];
		}
		if(n+c>0){
			e+=1;
		}
		else{
			e+=0;
		}
	}
	cout << e;
	return 0;
} 

Measured memory_bytes: 256
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*                                                    
      I ♥ CLARICE STARLING...                                                               
        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
const ll INF = (ll)2e18 + 77;
int n,m,x;
vector<vector<int>>M;
vector<int>cost;
bool check(vector<int>&a)
{
    int i;
    fo(i,0,m)if(a[i]<x)return true;
    return false;
}
ll recursion(int pos,vector<int>&a)
{
    if(pos==n)
    {
        if(check(a))return INF;
        else return 0;
    }
    
    if(check(a))
    {
        int i;
        fo(i,0,m)a[i]+=M[pos][i];
        ll ans=cost[pos]+recursion(pos+1,a);
        fo(i,0,m)a[i]-=M[pos][i];
        ans=min(ans,recursion(pos+1,a));
        return ans;
    }
    else 
    return 0;
}
void solve()
{
   cin>>n>>m>>x;
   M=vector<vector<int>>(n,vector<int>(m));
   cost=vector<int>(n);
   int i,j;
   fo(i,0,n)
   {
    cin>>cost[i];
    fo(j,0,m)cin>>M[i][j];
   }
   vector<int>a(m,0);
   ll ans=recursion(0,a);
   if(ans==INF)ans=-1;
   
   cout<<ans<<"\n";
}
int main()
{
   fastio
   //Test_cases
   solve();
  return 0;
}
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>
//if you want to apply lowerbound on set use s.lower_bound(key),not the one used for vector
// Syntax to create a min heap for priority queue priority_queue <int, vector<int>, greater<int>>; 
//for modinverse use modularexponention(x,M-2,M);
//for "each" subtraction from ans(ans-k) if(ans<0) do ans+=MOD,ans%=MOD
//vector<vector<int>>dp(201,vector<int>(n+1)); A way to initialize vector of vector
//If wrong on pretest 2 means logically wrong


/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/


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

using namespace std;

int main() {
  string s;
  cin >> s;
  long long k;
  cin >> k;
  int cnt = 0;
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == '1') {
      cnt++;
    } else {
      break;
    }
  }
  if (k <= cnt) {
    cout << 1 << '\n';
    return 0;
  }
  for (int i = 0; i < s.length(); i++) {
    if (s[i] != '1') {
      cout << s[i] << '\n';
      return 0;
    }
  }

  return 0;
}


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

# E[i]: 頂点iから伸びる頂点の集合
E = [[] for _ in range(N)]
# parent_cnt[i]: 頂点iの親
parent_cnt = [0] * N
for _ in range(N-1+M):
    A,B = map(int,input().split())
    E[A-1].append(B-1)
    parent_cnt[B-1] += 1

# 根を見つける
for i,num in enumerate(parent_cnt):
    if num == 0:
        root = i
        break

parent = [None] * N
parent[root] = 0

q = [root]
# DFS O(N+M)
while q:
    qq = []
    for V in q:
        for Vto in E[V]:
            parent_cnt[Vto] -= 1

            # 親が決定
            if parent_cnt[Vto] == 0:
                parent[Vto] = V + 1
                qq.append(Vto)
    
    q = qq

print(*parent, sep="\n")

Measured memory_bytes: 25172
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <utility>
#include <iomanip>

using namespace std;
using int64 = long long;

struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

int main() {
    int a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
}


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

int main(){
  int N,K;
  string S;
  cin >> N >> S >> K;
  for (int i=0;i<N;i++){
    if(S[i]!=S[K-1]) S[i]='*';
  }
  cout << S << endl;
}


Measured memory_bytes: 256
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    l = []
    INF = 10**12
    v = INF

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].append(B)
        l.append((A, B))

    ans = []
    for i, j in l:
        INF = 10**12
        dist = [-1]*(N+1)
        prev = [-1]*(N+1)
        dist[j] = 0
        prev[j] = 0
        q = deque([j])

        while q:
            a = q.popleft()
            for b in d[a]:
                if dist[b]==-1:
                    dist[b] = dist[a]+1
                    prev[b] = a
                    q.append(b)

        if v>dist[i]+1 and dist[i]!=-1:
            v = dist[i]+1
            buf = i
            ans = []
            while buf:
                ans.append(buf)
                buf = prev[buf]

    if ans:
        print(len(ans))
        for i in ans:
            print(i)
    else:
        print(-1)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 45788
#include <stdio.h>
#include <math.h>
int pwise(int b);
int a[10000006]={0};
int gcd(int a,int b);
int main(int argc, char *argv[])
{
	int n,i,j,gd,pair=1,set=0;
	scanf("%d",&n);
	int b[n];
	for(i=0;i<n;i++){
		scanf("%d",&b[i]);
		a[i]=0;
	} 
	
	gd=b[0];
	for(i=1;i<n;i++)
		gd=gcd(gd,b[i]);
	if(gd==1)set=1;
	for(i=0;i<n;i++){
		pair=pwise(b[i]);
		if(!pair)break;
	}
	if(pair)
		printf("pairwise coprime\n");
	else if(set)
		printf("setwise coprime\n");
	else
		printf("not coprime\n");
}
int gcd(int a,int b){
	int tmp;
	while(a!=0){
		tmp=a;
		a=b%a;
		b=tmp;
	}
	return b;
}
int pwise(int b){
	int i,pair=1,x,y;
	for(i=1;i*i<=b;i++){
		if(!(b%i)){
			y=b/i;x=i;
			if(y!=x){
				if(a[x]||a[y]){
					pair=0;break;
				}
				else{
					if(x!=1)
					a[x]=1;a[y]=1;
				}
			}
			else{
					if(a[x]){
						pair=0;break;
					}
					else
						if(x!=1)
						a[x]=1;
			}
		}
		
	}
	return pair;
}
					

Measured memory_bytes: 9424
#include <stdio.h>

int main()
{
	int i, N, C[50 + 1], V[50 + 1], ans = 0;

	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &V[i]);
	}
	for (i = 0; i < N; i++) {
		scanf("%d", &C[i]);
	}

	for (i = 0; i < N; i++) {
		if (V[i] > C[i]) {
			ans += V[i] - C[i];
		}
	}

	printf("%d", ans);

	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <deque>
#include <string>
 
using namespace std;
 
int main(void){
  int n,a,q,i,temp=0,qtemp;
  char s[10];
  deque<int> time,ftime;
  deque<string> name,fname;
 
  cin >> n >> q;
  qtemp=q;
  for(i=0;i< n;i++){
    cin >> s >> a;
    name.push_back(s);
    time.push_back(a);
  }
 
  while(!name.empty()){
    i=time.front()-q;
    if(i<=0){
      temp += time.front();
      fname.push_back(name.front());
      name.pop_front();
      ftime.push_back(temp);
      time.pop_front();
    }
    else{
      time.pop_front();
      time.push_back(i);
      name.push_back(name.front());
      name.pop_front();
      temp += qtemp;
    }
  }
 
  for(i=0;i<n;i++){
    cout << fname[i] << " "  << ftime[i] << endl;
  }
}


Measured memory_bytes: 5636
from collections import deque

N=int(input())
array = list(map(int,input().split()))
# N=3
# array=2,3,1

dict1={}
for i in range(N):
  dict1.update({i+1:array[i]})
dct = sorted(dict1.items(), key=lambda x:x[1])

for num in dct:
  print(str(num).split(",")[0].lstrip("("),end=" ")

Measured memory_bytes: 26588
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N;
  cin>>N;
  string S;
  cin>>S;
  string ans;
  bool flag=1;
  rep(j,0,4){
    bitset<100001> A(j);
    rep(i,0,N-1){
      if(A.test(i+1)){
        if(S[i+1]=='o'){
          if(A.test(i))
            A.set(i+2);
        }
        else{
          if(!A.test(i))
            A.set(i+2);
        }
      }
      else{
        if(S[i+1]=='o'){
          if(!A.test(i))
            A.set(i+2);
        }
        else{
          if(A.test(i))
            A.set(i+2);
        }
      }
    }
    bool F=0;
    if((A.test(0)&&A.test(N))||(!A.test(0)&&!A.test(N))){
    if(S[0]=='o'){
      if(A.test(0)){
        if(A.test(1)){
          if(A.test(N-1))
            F=1;
        }
        else{
          if(!A.test(N-1))
            F=1;
        }
      }
      else{
        if(A.test(1)){
          if(!A.test(N-1))
            F=1;
        }
        else{
          if(A.test(N-1))
            F=1;
        }
      }
    }
    else{
      if(A.test(0)){
        if(A.test(1)){
          if(!A.test(N-1))
            F=1;
        }
        else{
          if(A.test(N-1))
            F=1;
        }
      }
      else{
        if(A.test(1)){
          if(A.test(N-1))
            F=1;
        }
        else{
          if(!A.test(N-1))
            F=1;
        }
      }
    }
  }
    if(F){
      flag=0;
      rep(i,0,N){
        if(A.test(i))
          ans+='S';
        else
          ans+='W';
      }
      break;
    }
  }
  if(flag)
    ans="-1";
  cout<<ans<<endl;
  }



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

a2 = True
b2 = False
if a % 2 != 0:
    a0 = a
    a += 1
    a2 = False
if b % 2 == 0:
    b0 = b
    b -= 1
    b2 = True

c = b-(a-1)
if c % 2 == 0:
    if (c // 2) % 2 == 0:
        ans = 0
    else:
        ans = 1 
elif ((c-1) // 2) % 2 == 0:
    ans = 0 ^ b
else:
    ans = 1 ^ b
    
if a2 == False:
    ans = ans ^ a0
if b2 == True:
    ans = ans ^ b0

print(ans)    

Measured memory_bytes: 3064
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INTINF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
	int ans = 0;
	int tmp;
	int n; 
	cin >> n;
	if(n % 10 == 3) cout << "bon" << endl;
	else if(n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) cout << "pon" << endl;
	else cout << "hon" << endl; 
}

Measured memory_bytes: 3632
#include<iostream>
#include <math.h>

using namespace std;

int main() {
	int A;
	int B;
	double C;
	double shousu;

	cin >> A >> B;

	C = (double)(A + B) / 2;

	shousu = C - (int)C;

	if (shousu > 0) cout << "IMPOSSIBLE" << endl;
	else cout << (int)C << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main{

    void solve(){
        Scanner sc = new Scanner(System.in);

        while(true){
            int w = sc.nextInt();
            int d = sc.nextInt();
            if(w==0 && d==0) break;

            int[] front = new int[w];
            int[] side = new int[d];
            for(int i=0; i<w; i++) front[i] = sc.nextInt();
            for(int i=0; i<d; i++) side[i] = sc.nextInt();

            int cnt = 0;
            for(int i=0; i<d; i++){
                boolean boo = false;
                for(int j=0; j<w; j++){
                    if(side[i]==front[j]){
                        front[j] = -1;
                        cnt += side[i];
                        boo = true;
                        break;
                    }
                }
                if(!boo) cnt += side[i];
            }

            for(int i=0; i<w; i++){
                if(front[i]!=-1) cnt += front[i];
            }

            System.out.println(cnt);
        }
    }

    public static void main(String[] args){
        new Main().solve();
    }
}

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

namespace ConsoleApp53
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] c = new int[20];
            int w = 0;
            while (true)
            {

                int a = int.Parse(Console.ReadLine());
                if (a == 0)
                    break;
                int sum = 0;
                int[] b = new int[a];
                for (int j = 0; j < a; j++)
                {
                    b[j] = int.Parse(Console.ReadLine());
                    sum += b[j];
                }
                sum -= b.Max() + b.Min();
                c[w]=(sum / (a - 2));
                w++;
            }
            for(int j=0; j<w; j++)
            {
                Console.WriteLine(c[j]);
            }
        }
    }
}

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

int main(){
    string s,t;
    cin >> s >> t;
    int a,b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(u ==s) cout << a-1 << " " << b << endl;
    else cout << a << " " << b-1 << endl;


    return 0;
}

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

public class Main 
{
	static long best = 9999999999999l;
	static void go(int[] or)
	{
//		System.out.println("Try: " +Arrays.toString(or));
		
		long cur = 0;
		long remtar = g;
		for(int i = 0; i < d && remtar > 0; i++)
		{
			long nobon = remtar/((or[i]+1)*100);
			if(remtar%((or[i]+1)*100)!=0)nobon++;
			
			if(nobon < pro[or[i]])
			{ //do this many problems only
				cur += nobon;
				break;
			}
			else
			{
				cur += pro[or[i]];
				remtar -= pro[or[i]] * ((or[i]+1)*100);
				remtar -= bon[or[i]];
			}
		}
		best = Math.min(cur, best);
	}

	static void permutate(int[] cur, int i)
	{
		com++;
		for(int j = i; j < d; j++)
		{
			int[] cl = cur.clone();
			if(i!=j)
			{ //swap i and j
				cl[i] = cl[i] + cl[j];
				cl[j] = cl[i] - cl[j];
				cl[i] = cl[i] - cl[j];
			}
			permutate(cl, i+1);
		}
		
		if(i==d)
		{
			tot++;
//			System.out.println(i +" after: " +Arrays.toString(cur));
			go(cur);
		}
	}
	
	static int d;
	static int tot = 0;
	static int com = 0;
	static int g;
	static long[] bon;
	static long[] pro;

	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		d = sc.nextInt();
		g = sc.nextInt(); //target score
		bon = new long[d];
		pro = new long[d];
		
		for(int i = 0; i < d; i++)
		{
			pro[i] =  sc.nextInt();
			bon[i] = sc.nextInt();
		}
		int[] init = new int[d];
		for(int i = 0; i < d; i++)
			init[i] = i;
		
		permutate(init, 0);
		
//		System.out.println("Test : " + Arrays.toString(init));
//		System.out.println(tot + " " + com);
		
		System.out.println(best);
	}
}


Measured memory_bytes: 150656
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        n: Chars
    };

    let sum = n
        .into_iter()
        .map(|ch| ch.to_digit(10).unwrap() as usize)
        .sum::<usize>();
    let res = if sum % 9 == 0 { "Yes" } else { "No" };
    println!("{}", res);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 2488
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define INF 1145141919364364
#define int long long
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, m, v, p, a[100000];
int ans;
int x, y;
int cnt;

signed main() {
	cin >> n >> m >> v >> p;
	for (int i = 0; i < n; i++)cin >> a[i];
	sort(a, a + n);
	reverse(a, a + n);
	ans = p;
	x = p - 1;
	y = a[p - 1];
	for (int i = x + 1; i < n; i++) {
		if (x + (n - i - 1) + 1 >= v) {
			if (y <= a[i] + m) {
				ans++;
			}
		}
		else {
			int k = i - x - (v - (x + (n - i - 1) + 1));
			int s = cnt + (y - a[i])*(i - x);
			if (y <= a[i] + m && m*k >= s) {
				ans++;
			}
		}
		cnt += (a[i] - y);
	}
	cout << ans << endl;
}

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

using namespace std; 

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	string s;
	cin >> s;
	if(s[0] == s[1] and s[2] == s[0]) {
		cout << "No\n";
	}
	else cout << "Yes\n";


	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<(x)<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
int vis[maxn];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    
    for(int gap=m,i=1;gap>=1;gap-=2){
        cout<<i<<' '<<i+gap<<endl;
        i++;
    }
    for(int gap=m-1,i=1+m+1;gap>=1;gap-=2){
        cout<<i<<' '<<i+gap<<endl;
        i++;
    }
}
/* 
性质 构造尝试*3
 */

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

int main(){
  int A,B,C=0;
  cin >> A >> B;
  for(int i=0; i<2; i++){
    if(A>=B){
      C+=A;
      A--;
    }
    else{
      C+=B;
      B--;
    }
  }
  cout << C << endl;
}

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 endl "\n"
#define int long long
int32_t main()
{
    IOS
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout); 
    // #endif
    int n;
    cin>>n;
    int a[n][3];
    for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1]>>a[i][2];
	for(int i=1;i<n;i++) {for(int j=0;j<3;j++) {int maxx=-1; for(int k=0;k<3;k++) {if(k!=j) {maxx=max(maxx,a[i-1][k]);}} a[i][j]+=maxx;}}
    cout<<max(a[n-1][0],max(a[n-1][1],a[n-1][2]));
    return 0;
}

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

int main(){
    int n ;
    cin >> n ;
    map<string,int> mp ;
    rep(i,n){
        string s ;
        cin >> s ;
        mp[s]++ ;
    }
    int count = 0 ;
    for( auto p : mp ){
        count++ ;
    }
    if(count == 3 )cout << "Three" << endl ;
    if(count == 4 )cout << "Four" << endl ;
}

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

using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mp make_pair
#define ld long double
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int> > small_heap;
typedef priority_queue<int> big_heap;
const int N = 5e3 + 100;
const ll mod = 1e9 + 7;
int T;
ll ans;
vector<int> v;
ll dp[N];
int f[N], s[N], si[N], a[N], n, k;

int getfa(int x) { return f[x] == x ? x : f[x] = getfa(f[x]); }

ll ksm(ll a, ll b) {
    ll c = 1;
    for (; b; b >>= 1) {
        if (b & 1) c = (ll) c * a % mod;
        a = (ll) a * a % mod;
    }
    return c % mod;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]), f[i] = i;
    for (int i = 1; i <= n; i++)if (a[i] != -1)f[getfa(i)] = getfa(a[i]);
    for (int i = 1; i <= n; i++)if (a[i] == -1)s[getfa(i)]++;
    for (int i = 1; i <= n; i++)si[getfa(i)]++;
    for (int i = 1; i <= n; i++)
        if (f[i] == i) {
            if (s[i] == 0)ans++;
            else v.push_back(si[i]);
        }
    k = v.size();
    dp[0] = 1;
    for (int i = 0; i < k; i++)
        for (int j = i + 1; j >= 1; j--) {
            dp[j] = (dp[j] + dp[j - 1] * v[i] % mod * max(j - 1, 1) % mod) % mod;
        }
    ans = ans * ksm(n - 1, k) % mod;
    for (int i = 2; i <= k; i++)ans = (ans + ksm(n - 1, k - i) * dp[i]) % mod;
    for (int i = 0; i < k; i++)ans = (ans + ksm(n - 1, k - 1) * (v[i] - 1) % mod) % mod;
    ans = (n * ksm(n - 1, k) % mod - ans + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3960
fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let mut n: usize = it.next().unwrap().parse().unwrap();
    let k: usize = it.next().unwrap().parse().unwrap();
    let mut ans = 0;
    while n > 0 {
        ans += 1;
        n /= k;
    }
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a,b,i,ans=0,j;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
for(j=a;j<=b;j++)
{
ans++;
}

}

cout<<ans<<endl;

}


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

typedef long long ll;

int main() {
     
     int t = 1;
 //    cin>>t;

     while(t--){
        ll n, m;
        cin>>n>>m;
        cout<<n*(n-1)/2+(m-1)*m/2<<"\n";      
     }
    return 0;
}


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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int a, b, c; cin >> a >> b >> c;

	if(b-a == c-b) cout << "YES" << endl;
	else cout << "NO" << endl;


	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n)                                      \
  cerr << __LINE__ << ": " << #x << " = {";                   \
  for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];                   \
  cerr << "}" << '\n'
#define debugMatrix(x, h, w)                                         \
  cerr << __LINE__ << ": " << #x << " =\n";                          \
  for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) {      \
    cerr << ((hoge ? " {" : "{{"));                                  \
    for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga))      \
      cerr << ((fuga ? ", " : "")) << x[hoge][fuga];                 \
    cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
  }
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  long long N, X, M;
  cin >> N >> X >> M;
  map<long long, pair<long long, long long>> mp;
  int cnt = 0;
  long long A = X % M;
  long long sum = X - A;
  while (1) {
    if (A == 0) {
      cout << sum << '\n';
      return 0;
    }
    if (cnt == N) {
      cout << sum << '\n';
      return 0;
    }
    if (mp.count(A)) {
      break;
    }
    mp[A] = make_pair(cnt, sum);
    sum += A;
    cnt++;
    A = A * A % M;
  }
  int prev, psum;
  tie(prev, psum) = mp[A];
  N -= prev;
  cnt -= prev;
  long long ans = N / cnt * (sum - psum) + psum;
  N %= cnt;
  for (int i = 0; i < N; i++) {
    ans += A;
    A = A * A % M;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 6720
#include<stdio.h>   //A - Product

int main(){

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

    if((a*b)%2==1){
        //奇数のとき
        printf("Odd\n");
    }else{
        //偶数のとき
        printf("Even\n");
    }

    return 0;
}

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

const long long MOD = 1e9 + 7;
const int HW_MAX = 1000;
long long dp[HW_MAX + 1][HW_MAX + 1] = {0};

int main() {
  int H, W; cin >> H >> W;
  dp[0][0] = 1;
  for(int h = 0; h < H; h++){
    for(int w = 0; w < W; w++){
      char a; cin >> a;
      if (a == '#') {dp[h][w] = 0; continue;}
      
      if(h - 1 >= 0) dp[h][w] += dp[h - 1][w];
      if(w - 1 >= 0) dp[h][w] += dp[h][w - 1];
      dp[h][w] %= MOD;
    }
  }
  
  cout << dp[H-1][W-1] << endl;
}

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

int main(void){

  char *S;
  int len = 0;
  int i;

  S = (char*)malloc(10000);

  scanf("%[^\n]", S);

  while(S[len]){
    len++;
  }

  for(i = 0; i < len; i++){
    if('a' <= S[i] && S[i] <= 'z'){
      S[i] += 'A' - 'a';
    }else if('A' <= S[i] && S[i] <= 'Z'){
      S[i] += 'a' - 'A';
    }
  }

  for(i = 0; i < len; i++){
    printf("%c", S[i]);
  }

  printf("\n");

  free(S);

  return 0;
}


Measured memory_bytes: 2068