akhauriyash/Code-Regression huggingface dataset:
#ifdef _WIN32
#include "stdc++.h"
#else
#include <bits/stdc++.h>
#endif

// 継承可能な型
template <class Type>
struct IN : Type
{
	IN()
	{
		std::cin >> *this;
	}
};

// 継承不可能な型
template <class Type>
struct IN_
{
	Type val;

	IN_()
	{
		std::cin >> val;
	}

	operator Type&()
	{
		return val;
	}

	IN_<Type>& operator=(const Type& _value)
	{
		val = _value;
		return *this;
	}
};

template <class Char, class Type>
std::basic_ostream<Char>& operator <<(std::basic_ostream<Char>& os, const IN_<Type>& value)
{
	return os << value.val;
}

template <class Char, class Type>
std::basic_istream<Char>& operator >>(std::basic_istream<Char>& is, IN_<Type>& value)
{
	return is >> value.val;
}

template <class Type>
void OUT(const Type& value)
{
	std::cout << value << std::endl;
}

template <class Type, class ... Args>
void OUT(const Type& value, const Args& ... args)
{
	std::cout << value << ' ';
	OUT(args...);
}

using ll = long long;
using inll = IN_<ll>;
using vll = std::vector<ll>;
using setll = std::set<ll>;
using msetll = std::multiset<ll>;
using instr = IN<std::string>;

#define FOR(i, m, n) for (ll (i) = (m); (i) < (n); ++(i))
#define REP(i, n) for (ll (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for (ll (i) = (n); (i) >= 0; --(i))
#define ITRREP(it, v) for (auto (it) = (v).begin(); (it) != (v).end(); ++(it))
#define ITRREPR(it, v) for (auto (it) = (v).rbegin(); (it) != (v).rend(); ++(it))
#define DIVUP(a, b) (((a) + (b) - 1) / (b))

void Main();

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

	Main();

#ifdef _DEBUG
	system("pause");
#endif

	return 0;
}

using namespace std;

//////////////////////////////

struct Node
{
	int cost;
	Node* prev;
	vector<Node*> to;
	bool able, done;
};

void Main()
{
	inll h, w;
	vector<vector<Node>> s;
	s.resize(h);
	ll painted = 0;

	REP(i, h)
	{
		s[i].resize(w);
		instr s_;
		REP(j, w)
		{
			s[i][j] = { 999, nullptr, vector<Node*>(), s_[j] == '.', false };

			if (s_[j] == '#')
				painted++;
		}
	}

	REP(i, h)
	{
		REP(j, w)
		{
			if (i != 0 && s[i - 1][j].able)
			{
				s[i][j].to.push_back(&s[i - 1][j]);
			}
			if (j != 0 && s[i][j - 1].able)
			{
				s[i][j].to.push_back(&s[i][j - 1]);
			}
			if (i != h - 1 && s[i + 1][j].able)
			{
				s[i][j].to.push_back(&s[i + 1][j]);
			}
			if (j != w - 1 && s[i][j + 1].able)
			{
				s[i][j].to.push_back(&s[i][j + 1]);
			}
		}
	}

	s[0][0].cost = 0;

	while(true)
	{
		Node *processNode = nullptr;

		REP(i, h)
		{
			REP(j, w)
			{
				Node& node = s[i][j];

				if(node.done || node.cost < 0)
					continue;

				if(processNode == nullptr)
				{
					processNode = &node;
					continue;
				}

				if (node.cost < (*processNode).cost) {
					processNode = &node;
				}
			}
		}

		if (processNode == nullptr) {
			break;
		}

		(*processNode).done = true;

		for (auto* to : processNode->to)
		{
			int newCost = processNode->cost + 1;

			if ((to->cost < 0) || (to->cost > newCost)) {
				to->cost = newCost;
				to->prev = processNode;
			}
		}
	}

	if (s[h - 1][w - 1].cost == 999)
	{
		return OUT(-1);
	}

	return OUT(w * h - painted - s[h - 1][w - 1].cost - 1);
}


Measured memory_bytes: 512
n = int(input())
A = list(map(int, input().split()))

mod = 10**9+7

import fractions
#import math
from functools import reduce
def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)
  #return (x * y) // math.gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

l = lcm_list(list(A))
ans = 0
for i in range(n):
    ans += l//A[i]
print(ans%mod)

Measured memory_bytes: 5624
while True:
    (H, W) = [int(x) for x in input().split()]
    if H == W == 0:
        break
  
    for hc in range(H):
        for wc in range(W):
            if (hc + wc)  % 2 == 0:
                print('#', end='') 
            else:
                print('.', end='')
        print()
    print()

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

const ll INF = 1000000007;
const ll MAX_N = 100010;
ll res;
ll N, K;
vector<vector<ll>> G(MAX_N, vector<ll>(0));
vector<bool> gone(MAX_N, false);

void dfs(ll x) {
  gone[x] = true;
  ll cnt = 0;
  for (auto g : G[x]) {
    if (!gone[g]) {
      cnt++;
    }
  }
  if (x == 0) {
    rep(i, cnt) {
      res *= (K-1-i);
      res %= INF;
    }
  }
  else {
    rep(i, cnt) {
      res *= (K-2-i);
      res %= INF;
    }
  }
  for (auto g : G[x]) {
    if (!gone[g]) {
      dfs(g);
    }
  }
}

int main() {
  cin >> N >> K;
  rep(i, N-1) {
    ll a, b;
    cin >> a >> b;
    --a; --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  res = K;
  dfs(0);
  cout << res << endl;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define li long int
#define ll long long int
#define vec(x) vector<x> 
#define st(x) set<x> 
#define mpp(x,y) map<x,y>
#define qq(x) queue<x>
#define pqq(x) priority_queue<x> 
#define pi(x,y) pair<x,y>
#define forf(i,x,y) for(ll i=x;i<y;i++)
#define forl(i,x) for(ll i=x-1;i>=0;i--)
#define rev(x) reverse(x.begin(),x.end())
#define mem(x,a) memset(x,a,sizeof(x))
#define mod 1000000007
#define nxt_per(x) next_permutation(x.begin(),x.end())
#define pb push_back
#define pob pop_back
#define pp push
#define po pop
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define vp(x,y) vec(pi(x,y) )
#define vv(x) vector<vector<x> >
#define all(x) x.begin(),x.end()

using namespace std;

int main()
{
	fastio;
	/*#ifndef ONLINE_JUDGE
    	freopen("input.txt","r",stdin);
    	freopen("output.txt","w",stdout);
	#endif*/
	
	int a,b;
	cin>>a>>b;
	int ans=a*b-(a+b-1);
	cout<<ans;
	return 0;
}

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

const int zero = 15000;
const int d = 13000;
int h, w, c[100][100];
bool dp[100][100][30000];

int main()
{
    cin >> h >> w;
    rep(i, h) rep(j, w)
    {
        cin >> c[i][j];
    }
    rep(i, h) rep(j, w)
    {
        int tmp; cin >> tmp;
        c[i][j] = abs(c[i][j] - tmp);
    }
    //rep(i, h) {rep(j, w) cerr << c[i][j] << " "; cerr << endl;}

    rep(i, h) rep(j, w) for(int k = zero - d; k <= zero + d; k++)
    {
        dp[i][j][k] = false;
    }

    dp[0][0][zero + c[0][0]] = dp[0][0][zero - c[0][0]] = true;
    for (int i = 1; i < h; i++)
    {   
        for (int j = zero - d; j <= zero + d; j++)
        {
            if(dp[i - 1][0][j])
            {
                dp[i][0][j + c[i][0]] = true;
                dp[i][0][j - c[i][0]] = true;
            }
        }
    }
    for (int i = 1; i < w; i++)
    {
        for (int j = zero - d; j <= zero + d; j++)
        {
            if(dp[0][i - 1][j])
            {
                dp[0][i][j + c[0][i]] = true;
                dp[0][i][j - c[0][i]] = true;
            }
        }
        
    }
    
    for (int i = 1; i < h; i++)
    {
        for (int j = 1; j < w; j++)
        {
            for (int k = zero - d; k <= zero + d; k++)
            {
                if(dp[i - 1][j][k] || dp[i][j - 1][k])
                {
                    dp[i][j][k + c[i][j]] = true;
                    dp[i][j][k - c[i][j]] = true;
                }
            }
            
        }
    }
    
    int res = 1000;
    for (int i = zero - d; i <= zero + d; i++)
    {
        if(dp[h - 1][w - 1][i])
        {
            res = min(res, abs(i - zero));
        }
    }
    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 235776
import java.util.Scanner;

public class Main
{
	public static void main(String[]args)
	{
		Scanner scn = new Scanner(System.in);
		int ques = scn.nextInt();
		int ans = 1;
		for(int a= 0;a<3;a++)
		{
			ans = ans*ques;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21204
#include <stdio.h>

int main(){
  int a,b,c;
  int x=0,y=0;
  while(scanf("%d,%d,%d", &a, &b, &c)!=EOF){
    if(a==b) y++;
    else if(a*a+b*b == c*c) x++;
  }

  printf("%d\n%d\n", x,y);
}

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

int main() {
  int n;
  cin >> n;
  vector<int> x(n), y(n);
  rep(i,n) cin >> x[i] >> y[i];
  // 距離を求める関数(ラムダ式:無名関数)
  auto dist = [&](int i, int j) {
    double dx = x[i]-x[j];
    double dy = y[i]-y[j];
    return sqrt(dx*dx+dy*dy);
  };

  double len = 0;
  rep(i,n)rep(j,i){
    len += dist(i,j);
  }
  int num = 2;
  for (int i = n-1; i>=1; --i) num *= i;
  int fact = 1;
  for (int i = n; i>=1; --i) fact *= i;
  double ans = (len*num)/fact;
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 256
#!python3

def LI():
    return list(map(int, input().split()))

# input
N, K = LI()
S = input()


def main():
    ans = list(S)
    d = {
        "A": "a",
        "B": "b",
        "C": "c"
    }
    
    ans[K - 1] = d[S[K - 1]]
    print("".join(ans))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
def isCLKWISE(ph):
    if (ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0 : return False
    else : return True
     
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) : break
            else :
                del phU[-2]
                if len(phU) == 2 : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) : break
            else :
                del phL[-2]
                if len(phL) == 2 : break
    ph = phU + phL[1:-1]
    return ph
 
n = int(input())
P = []
for i in range(n):
    P.append([int(x) for x in input().split()])
     
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

Measured memory_bytes: 33548
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cmath>
#include <set>
#include <bitset>
#include <limits>

using namespace std;

#define ll long long

// int check(int i, int j, int k){
//     int flag = 1;
//     if(j-i == k-j){
//         flag = 0;
//     }else if(k-i == j-k){
//         flag = 0;
//     }else if(i-j == k-i){
//         flag = 0;
//     }else if(j-k == i-j){
//         flag = 0;
//     }else if(i-k == j-i){
//         flag = 0;
//     }else if(k-j == i-k){
//         flag = 0;
//     }

//     return flag;
// }

int main(void){
    int n;
    cin >> n;
    string s;
    cin >> s;
    //cout << s.max_size() << endl;

    vector<int> r, g, b;

    r.reserve(n);
    g.reserve(n);
    b.reserve(n);

    for(int i = 0;i < n;++i){
        if(s[i] == 'R'){
            r.push_back(i+1);
        }else if(s[i] == 'G'){
            g.push_back(i+1);
        }else{
            b.push_back(i+1);
        }
    }

    sort(b.begin(), b.end());

    ll ans = 0;
    for(int ri = 0;ri < (int)r.size();++ri){
        for(int gi = 0;gi < (int)g.size();++gi){
            ans += (ll)b.size();
            int i, j;
            if(r[ri] > g[gi]){
                i = g[gi];
                j = r[ri];
            }else{
                i = r[ri];
                j = g[gi];
            }

            if(binary_search(b.begin(), b.end(), 2*i-j)){
                ans -= 1LL;
            }
            if((i+j)%2 == 0){
                if(binary_search(b.begin(), b.end(), (i+j)/2)){
                    ans -= 1LL;
                }
            }
            if(binary_search(b.begin(), b.end(), 2*j-i)){
                ans -= 1LL;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3664
#include <stdio.h>

#define len 5

int main(void) {
  int x1, x2, x3, x4, x5;
  int x[len];
  int index;
  scanf("%d%d%d%d%d", &x1, &x2, &x3, &x4, &x5);
  x[0] = x1;
  x[1] = x2;
  x[2] = x3;
  x[3] = x4;
  x[4] = x5;
  for(int i = 0; i < len; i++) {
    if(x[i] == 0) {
      index = i+1;
    }
  }
  printf("%d", index);
  return 0;
}


Measured memory_bytes: 1728
fun main(args: Array<String>) {
    abc106b()
}

fun abc106b() {
    val n = readLine()!!.toInt()

    val answer = (1..n).count { n1 ->
        (1..n1).filter { it % 2 != 0 }
            .count { n1.toDouble() % it.toDouble() == 0.toDouble() } == 8
    }

    println(answer)
}


Measured memory_bytes: 33652
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int cnt;

void insertionSort(int* A, int n, int g){
	for(int i = g; i < n; ++i){
		int v = A[i];
		int j = i - g;
		while(j >= 0 && A[j] > v){
			A[j + g] = A[j];
			j = j - g;
			cnt++;
		}
		A[j + g] = v;
	}
}

int main() {
	int n;
	cin >> n;
	int A[n];
	for(int i = 0; i < n; ++i){
		cin >> A[i];
	}
	
	cnt = 0;
	int m = 8;
	int G[] = {3280, 1093, 364, 121, 40, 13, 4, 1};
	
	int um = 0;
	vector <int> uG;
	
	for(int i = 0; i < m; ++i){
		if(G[i] > n) continue;
		uG.push_back(G[i]);
		um++;
		if(i != m - 1) cout << " ";
		else cout << endl;
		insertionSort(A, n, G[i]);
	}
	cout << um << endl;
	for(int i = 0; i < um; ++i){
		cout << uG[i];
		if(i == um - 1) cout << endl;
		else cout << " ";
	}
	cout << cnt << endl;
	// cout << (cnt <= ceil(pow(n, 1.5))) << endl;
	for(int i = 0; i < n; ++i){
		cout << A[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 7016
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict


x,n=MAP()
if n==0:
    print(x)
    exit()
a=LI()
l=-1;r=-1
for i in range(1000):
    if x-i not in a:
        l=x-i
        break
for i in range(1,101):
    if x+i not in a:
        r=x+i
        break
if abs(r-x)>=abs(l-x):
    print(l)
else:
    print(r)


Measured memory_bytes: 9384
n=int(input())
a=[-1]+list(map(int,input().split()))

t=((n+1)+2-1)//2

ans=[-1]+[0 for i in range(n)]
ans[t:]=a[t:]

for i in range(t-1,0,-1):
 t_sum=sum(ans[i+i::i])
 if a[i]%2==t_sum%2:
  ans[i]=0
 else:
  ans[i]=1

m=ans.count(1)
ans_l=[]
for i in range(n+1):
 if ans[i]==1:
  ans_l.append(i)
print(m)
if ans_l:
 print(*ans_l)

Measured memory_bytes: 14124
#pragma GCC optimize("Ofast")
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
#include<iomanip>
#include<queue>

const long long INF_L = 1e17+7;
const long long INF_I = 1e9+7;
const long long MOD = 1e9+7;
const double EPS = 1e-8;
const double PI=acos(-1);

using namespace std;


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n,k;
	cin >> n >> k;
	
	vector<int> h(n);
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	
	for(int i=0;i<k;i++){
		h.push_back(INF_I);
	}
	
	vector<int> dp(n,INF_I);
	dp[0]=0;
	
	for(int i=0;i<n;i++){
		for(int j=1;j<=k;j++){
			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
		}
	}
	
	cout << dp[n-1] << endl;
	
	return 0;
}


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

using namespace std;
typedef long long ll;
    
int main()
{
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());

    // cout << s << " " << t << endl;

    if (s < t) {
        cout << "Yes";
    } else {
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 256
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ll long long
#define INF 1000000000000000000

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <ios>
#include <iomanip>

using namespace std;

int main(){
    int A,B,K;
    cin >> A >> B >> K;
    int i=max(A,B);
    int count=0;
    int ans=0;
    while(count<K){
        if(A%i==0 && B%i==0){
            count++;
            ans=i;
        }
        i--;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

H,W,D=get_i
a=array(H)
H.times do|i|
    a[i]=get_i
end
pos_exc=array(H*W+1)
H.times do|i|
    W.times do|j|
        pos_exc[a[i][j]]=[i,j]
    end
end
cost=array(H*W+1,0)
1.upto(H*W-D) do|i|
  current=pos_exc[i]
  next_=pos_exc[i+D] 
  cost[i+D]=cost[i]+(next_[0]-current[0]).abs+(next_[1]-current[1]).abs
end
Q=gets.to_i
Q.times do
    l,r=get_i
    puts cost[r]-cost[l]
end

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

int main(){
    int N;
    std::cin >> N;
    std::vector< int > A(N);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }
    std::sort(A.begin(), A.end());
    std::vector< bool > en(1000001, true);

    int cnt = 0;
    for(int i=0; i<N; i++){
        if(!en[A[i]]){
            continue;
        }
        for(int j=A[i]; j<=1000001; j+= A[i]){
            en[j] = false;
        }
        if(i != N-1 && A[i+1] == A[i]){
            cnt--;
        }
        cnt++;
        
    }

    std::cout << cnt << std::endl;
    
    return 0;
}



Measured memory_bytes: 4316
A = int(input())
B = int(input())
C = int(input())
X = int(input())

couter = 0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500 * i + 100 * j + 50 * k == X:
                couter += 1
print(couter)

Measured memory_bytes: 3060
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long sum=0;
		int N = new java.util.Scanner(System.in).nextInt();
		for(int i =1;i<=N;i++){
			if(i%3!=0&&i%5!=0)sum+=i;
		
		}
				
		System.out.println(sum);

	}

	
	

}


Measured memory_bytes: 35632
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int x=0,w=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-48,c=getchar();
	return x*w;
}
const int N=1e5+5,mod=1e9+7;
int n,k;
int a[N],jc[N],inv[N];
int pre[N];
int QP(int x,int k){
	int ret=1;
	while(k){
		if(k&1)ret=ret*x%mod;
		k>>=1;
		x=x*x%mod;
	}
	return ret;
}
int C(int n,int m){
	if(n<m||m<0)return 0;
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
	n=read();k=read();
	if(k<=1){puts("0");return 0;}
	jc[0]=1;
	for(int i=1;i<=n;++i)a[i]=read(),jc[i]=jc[i-1]*i%mod;
	inv[n]=QP(jc[n],mod-2);
	for(int i=n;i>=1;--i)inv[i-1]=inv[i]*i%mod;
	sort(a+1,a+n+1);
	if(k==2)pre[0]=1;
	for(int i=1;i<=n;++i)pre[i]=(pre[i-1]+C(i,k-2))%mod;
	int ans=0;
	for(int i=2;i<=n;++i)ans=(ans+a[i]*pre[max(i-2,0ll)])%mod;
	for(int i=1;i<n;++i)ans=(ans-a[i]*pre[max(n-i-1,0ll)]%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	Int N;
	cin >> N;

	Int ans = 0;
	for (int a = 1; a <= N; ++a) {
		for (int b = 1; a * b < N; ++b) {
			++ans;
		}
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 3616
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

a, b = MAP()

if b >= a:
	print(a)
else:
	print(a-1)


Measured memory_bytes: 3944
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf = 1e9;

int H,W;
int cnt[30];
string s[15],sorts[15];
bool ok[15], ok2[15];
vector<pair<int, int>> vt,vt2;
int main(){
    cin>>H>>W;
    REP(i,0,H) cin>>s[i];
    if(H==1){
        REP(i,0,W){
            cnt[s[0][i]-'a']++;
            cnt[s[0][i]-'a']%=2;
        }
        bool ng=W%2;
        REP(i,0,30){
            if(cnt[i]%2==0){
                continue;
            }
            else if(cnt[i]%2 && ng){
                ng=false;
            }else{
                p("NO");
                return 0;
            }
        }
        p("YES");
        return 0;
    }
    if(W==1){
        REP(i,0,H){
            cnt[s[i][0]-'a']++;
            cnt[s[i][0]-'a']%=2;
        }
        bool ng=H%2;
        REP(i,0,30){
            if(cnt[i]%2==0){
                continue;
            }
            else if(cnt[i]%2 && ng){
                ng=false;
            }else{
                p("NO");
                return 0;
            }
        }
        p("YES");
        return 0;
    }
    REP(i,0,H) {
        sorts[i] = s[i];
        sort(sorts[i].begin(), sorts[i].end());
    }
    REP(i,0,H-1){
        if(ok[i]) continue;
        REP(j,i+1,H){
            if(ok[j]) continue;
            if(sorts[i]==sorts[j]){
                ok[i]=ok[j]=true;
                vt.emplace_back(i,j);
                break;
            }
        }
    }
    if(vt.size()!=H/2) {
        p("NO");
        return 0;
    }
    string ex;
    if(H%2) {

        REP(i, 0, H) {
            if (!ok[i]) {
                ex = s[i];
            }
        }
    }
    string t = s[vt[0].F];
    string u = s[vt[0].S];
    REP(i,0,W-1){
        if(ok2[i]) continue;
        REP(j,i+1,W){
            if(ok2[j]) continue;
            if(t[i]==u[j]&&t[j]==u[i]){
                ok2[i]=ok2[j]=true;
                vt2.emplace_back(i,j);
                break;
            }
        }
    }

    if(vt2.size()!=W/2) {
        p("NO");
        return 0;
    }

    string ex2 = "";
    if(W%2) {
        REP(j, 0, W) {
            if (!ok2[j]) {
                REP(i, 0, H) {
                    ex2 += s[i][j];
                }
            }
        }
    }
    for(auto v:vt){
        for(auto v2:vt2){
            if(s[v.F][v2.F]!=s[v.S][v2.S]){
                p("NO");
                return 0;
            }
        }
    }
    if(W%2) {
        for (auto v:vt) {
            if (ex2[v.F] != ex2[v.S]) {
                p("NO");
                return 0;
            }
        }
    }
    if(H%2) {
        for (auto v:vt2) {
            if (ex[v.F] != ex[v.S]) {
                p("NO");
                return 0;
            }
        }
    }
    p("YES");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int dp[3006][3006];
string s,t;
int cal(int i,int j){ 
    if(i==s.size()||j==t.size()) return 0;
    if(dp[i][j]!=-1)return dp[i][j];    
    int sol=max(cal(i+1,j),cal(i,j+1));
    if(s[i]==t[j])sol=max(sol,cal(i+1,j+1)+1);
    return dp[i][j]=sol;

} 
void bild(int i,int j){ 
    if(i==s.size()||j==t.size()) return ;
    if(cal(i+1,j)==cal(i,j)){ 
        bild(i+1,j);
        return ;
    } 
    if(cal(i,j+1)==cal(i,j)){ 
        bild(i,j+1);
        return;
    }
    if(cal(i+1,j+1)+1==cal(i,j)){  
        cout<<s[i];
        bild(i+1,j+1);
        return ;
    }
} 
int main()
{
    
    cin>>s;
    cin>>t;
    memset(dp,-1,sizeof dp);
    bild(0,0);    
        
    return 0;
}


Measured memory_bytes: 35968
n,x,*a = map(int,open(0).read().split())
INF = float("inf")
ref = [INF]*n
ans = INF
for i in range(n):
	ref = [min(ref[j],a[(j+i)%n]) for j in range(n)]
	ans = min(ans,sum(ref)+i*x)
print(ans)

Measured memory_bytes: 3316
/******************************************
* AUTHOR : DHRUV GUPTA *
* NICK : COSMOGOD *
* INSTITUTION : LNMIIT *
******************************************/

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000007

// for code with comments see submission number 6936679
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll n;
	cin >> n;
	double prob[n];
	for(ll i=0;i<n;i++)	
		cin >> prob[i];

	double dp[n+1][n+1];
	memset(dp,0,sizeof(dp));
	dp[1][0] = 1.0-prob[0];
	for(ll i=2;i<=n;i++){
		dp[i][0] = (1.0 - prob[i-1]) * dp[i-1][0];
	}

	dp[1][1] = prob[0];
	for(ll i=2;i<=n;i++){
		dp[i][i] = dp[i-1][i-1]*prob[i-1];
	}

	for(ll i=1;i<=n;i++){
		for(ll j=1;j<i;j++){
			dp[i][j] = (dp[i-1][j-1]*prob[i-1])+(dp[i-1][j])*(1-prob[i-1]);
		}
	}
	double ans = 0;
	for(ll i=n/2+1;i<=n;i++){
		ans += dp[n][i];
	}

	cout << fixed << setprecision(10) << ans;
	return 0;
}

Measured memory_bytes: 70656
L,R = map(int, input().split())

if R-L >= 2019:
    print(0)
else:
    ans = float('inf')
    for i in range(L, R+1):
        for j in range(L, R+1):
            if i == j:
                continue
            ans = min(ans, (i*j)%2019)
    print(ans)

Measured memory_bytes: 40428
#include <iostream>

#include <vector>

#include <algorithm>

using std::cin;
using std::cout;
using std::endl;

using std::vector;

using std::max;

static int
solve(int *count, int limit)
{
  int best = 0;
  for (int n = 0; n < limit - 2; n++)
  {
    best = max(best, count[n] + count[n + 1] + count[n + 2]);
  }
  return best;
}

int
main()
{
  int N;
  cin >> N;
  int count[100000] = {0};
  for (int n = 0; n < N; n++)
  {
    int a;
    cin >> a;
    count[a]++;
  }
  cout << solve(count, 100000) << endl;
  return 0;
}


Measured memory_bytes: 640
// https://atcoder.jp/contests/abc100/tasks/abc100_a

#include <iostream>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  int a, b;
  string r;

  cin >> a >> b;

  r = a <= 8 && b <= 8 ? "Yay!" : ":(";

  cout << r << '\n';

  return 0;
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int n, a;
    cin >> n;
    vector<int> c(n + 1);
    for (int i = 1; i < n; ++i) cin >> a, ++c.at(a);
    for (int i = 1; i <= n; ++i) cout << c.at(i) << endl;
    return 0;
}


Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;

int main() {
  string s, t;
  cin >> s >> t;
  cout << t << s << endl;
}

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

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

    int i;
    int count = 0;

    int N;
    cin >> N;

    int a[N];
    for(i = 0; i < N; i++)
    {
        cin >> a[i];
    }
    
    for(i = 0; i < N; i++)
    {    
        while((a[i] % 2) == 0)
        {
            a[i] = a[i] / 2;
            count++;
        }    
    }
    
    cout << count << "\n";

    return 0;
}

Measured memory_bytes: 256
n, k = gets.chomp.split(" ").map(&:to_i)
h = []
n.times do
    h << gets.chomp.to_i
end
h.sort!
ans = 1 << 40

(n-k+1).times do |i|
    tmp = h[i+k-1] - h[i]
    ans = ans > tmp ? tmp : ans
end

puts ans

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

using namespace std;

int main()
{
	string s;
	while(cin >> s)
	{
		
		int joi=0;
		int ioi=0;
		char bef='0';
		char befbef='0';

		for(int i=0;i<s.size();i++)
		{
			if(befbef=='J' and bef=='O' and s[i]=='I')
				joi++;
			if(befbef=='I' and bef=='O' and s[i]=='I')
				ioi++;

			befbef=bef;
			bef=s[i];
		}

		cout << joi << endl;
		cout << ioi << endl;
	}



}


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

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

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

	string s;
	cin >> s;

	if (s.size() == 3) {
		reverse(begin(s), end(s));
	}

	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
from heapq import *

N,*A = map(int, open(0).read().split())
ai = [x * (-1) for x in A]
heapify(ai)
ans = heappop(ai) * (-1)
searching = 1
for i in range(N-2):
    if i % 2 == 0:
        temp = heappop(ai) * (-1)
    ans += temp
print(ans)

Measured memory_bytes: 31796
#include "bits/stdc++.h"
using namespace std;

#define OUT(x)  cerr << #x << " = " << x << endl;
#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define pll     pair<long long, long long>
#define ll      long long

int main() {
        long long q, h, s, d;
        long long n;
        cin >> q >> h >> s >> d >> n;
        long long forone = min({4 * q, 2 * h, s});
        if (forone * 2 <= d) cout << forone * n << endl;
        else {
                long long div = n / 2;
                long long mod = n % 2;
                cout << div * d + mod * forone << endl;
        }
        return 0;
}



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

int main() {
    int h, n; scanf("%d %d", &h, &n);
    int summ = 0;
    for (int i=1; i<=n; i++) {
        int a; scanf("%d", &a);
        summ += a;
    }
    printf("%s\n", summ >= h ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 256
n,k,q=map(int,input().split())
point=list(k-q for _ in range(n))
ans=''
for i in range(q):
    x=int(input())
    point[x-1]+=1

for i in range(n):    
    if point[i]>0:
        ans+='Yes\n'
    else:
        ans+='No\n'
print(ans)

Measured memory_bytes: 8232
import java.util.Scanner;



public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s,m,h;
		s = sc.nextInt();

		h = s / 3600;
		m = (s%3600) / 60;
		s = s % 60;

		System.out.println(h + ":" + m + ":" + s);
	}

}



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

using namespace std;

int main()
{
    unsigned long n;
    cin>>n;
    unsigned long a[n],b[n],c[n],dp[3][n];
    for(unsigned long i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];

    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];
    for(unsigned long i=1;i<n;i++)
    {

        dp[0][i] = a[i] + max(dp[1][i-1], dp[2][i-1]);
        dp[1][i] = b[i] + max(dp[0][i-1], dp[2][i-1]);
        dp[2][i] = c[i] + max(dp[0][i-1], dp[1][i-1]);
        //cout << max(max(dp[0][i], dp[1][i]), dp[2][i])<<endl;
    }
    cout << max(max(dp[0][n-1], dp[1][n-1]), dp[2][n-1]);
    return 0;
}

Measured memory_bytes: 4864
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;

bool check(int a, int b) {
	return a > b;
}

int main() {
	int n;
	cin >> n;
	vllint a(n);
	rep(i, n) {
		cin >> a[i];
	}
	llint ans = a[0];
	rep(i, n - 1) {
		while (ans != 0 && a[i + 1] != 0) {
			if (ans < a[i + 1]) {
				a[i + 1] %= ans;
			}
			else {
				ans %= a[i + 1];
			}
		}
		ans = max(ans, a[i + 1]);
	}
	cout << ans << endl;
	return 0;
}


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

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

    int N; cin>>N;
    int i = 0;
    while (pow(10,i) <= N)
        i++;
    i--;
    int ans = 0;
    if (i % 2 == 0)
        ans += N-pow(10,i)+1;
    cerr << ans << endl;
    while (--i >= 0) {
        if (i%2 == 0)
            ans += 9*(pow(10,i));
        cerr << ans << endl;
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 512
using System;
class Program
{
	static void Main(string[] args)
	{
		string[] a = Console.ReadLine().Split();
		if (a[0] == "5" && a[1] == "5" && a[2] == "7") { Console.WriteLine("YES"); }
		else if (a[0] == "5" && a[1] == "7" && a[2] == "5") { Console.WriteLine("YES"); }
		else if (a[0] == "7" && a[1] == "5" && a[2] == "5") { Console.WriteLine("YES"); }
		else { Console.WriteLine("NO"); }
	}
}

Measured memory_bytes: 25596
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))

typedef long long ll;

int main() {
    int Q;
    cin >> Q;
    
    rep( i, Q) {
        ll A, B;
        cin >> A >> B;
        ll N = A*B;
        
        ll mid = sqrt((long double)(N-1));
        ll ans = mid*2;
        
        if ( A!=B ) ans--;
        if ( mid*(mid+1) >= N ) ans--;
        
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100
vector<vector<int>> grh;
vector<int> trail;
bool cycle = false;
void dfs(int crr) {
  if (trail[crr] == 1) {
    cycle = true;
    return;
  } else if (trail[crr] == 2) {
    return;
  }
  trail[crr] = 1;
  for (int nxt : grh[crr]) {
    dfs(nxt);
  }
  trail[crr] = 2;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  grh.resize(n);
  trail.resize(n);
  for (int i = 0; i < m; i++) {
    int s, t;
    cin >> s >> t;
    grh[s].push_back(t);
  }
  for (int i = 0; i < n; i++) {
    trail[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    if (!trail[i]) {
      dfs(i);
    }
  }
  if (cycle) {
    cout << 1 << '\n';
  } else {
    cout << 0 << '\n';
  }
  return 0;
}


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

template <typename T> void setmin(T& a, T b) {
	if (b < a) a = b;
}

using i64 = int64_t;
const i64 INF = 1e17;

map<int, i64> dp;

i64 query_pt(int x) {
	i64 ans = INF;
	auto it = dp.lower_bound(x);
	if (it != dp.end()) {
		setmin(ans, (it->first - x) + it->second);
	}
	if (it != dp.begin()) {
		--it;
		setmin(ans, (x - it->first) + it->second);
	}
	return ans;
}

void insert_pt(int x, i64 v) {
	if (query_pt(x) <= v) return;

	auto it = dp.lower_bound(x);
	while (it != dp.end()) {
		if (v + (it->first - x) <= it->second) {
			it = dp.erase(it);
		} else {
			break;
		}
	}
	while (it != dp.begin()) {
		--it;
		if (v + (x - it->first) <= it->second) {
			it = dp.erase(it);
		} else {
			break;
		}
	}
	dp[x] = v;
}

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

	int N, Q, A, B; cin >> N >> Q >> A >> B;

	dp[A] = 0;
	int prv = B;
	i64 cval = 0;
	for (int q = 0; q < Q; q++) {
		int x; cin >> x;

		int d = abs(x - prv);
		cval += d;

		insert_pt(prv, query_pt(x) - d);

		prv = x;
	}

	i64 ans = INF;
	for (auto it : dp) {
		setmin(ans, it.second);
	}
	ans += cval;
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<bool> flag(n, false);
  vector<ll> s;
  vector<ll> cycle;
  int now = 1;
  while (true) {
    s.push_back(now);
    now = a[now - 1];
    if (flag[now - 1] == true) {
      break;
    }
    flag[now - 1] = true;
  }
  for (int i = s.size() - 1; i >= 0; i--) {
    cycle.push_back(s[i]);
    if (s[i] == now) {
      break;
    }
  }
  reverse(all(cycle));
  if (k < s.size()) {
    cout << s[k] << endl;
  } else {
    cout << cycle[(k - s.size()) % cycle.size()] << endl;
  }
  return 0;
}

Measured memory_bytes: 9252
object Main extends App {
	val Array(h, w) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
	val a = Array.ofDim[Int](h, w)
 
	for(i<-0 until h){
		a(i) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
	}
 
	var ans = List[(Int, Int, Int, Int)]()
	
	for(i<-0 until h){
		for(j<-0 until w){
			if(a(i)(j)%2 != 0){
				if(j != w-1){
					a(i)(j+1) += 1
					ans = (i,j,i,j+1) :: ans
				}else if(i != h-1){
					a(i+1)(j) += 1
					ans = (i,j,i+1,j) :: ans
				}
			}
		}
	}


	println(ans.size)
	for(x <- ans.reverse){
		myP(x._1, x._2, x._3, x._4)
	}
 
	def myP(x: Int, y: Int, a: Int, b: Int): Unit = {
		println(Array(x+1,y+1,a+1,b+1).mkString(" "))
	}

}


Measured memory_bytes: 90648
import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
MOD = 10**9+7
sa = set(A)
sb = set(B)
ok = True
if len(sa) != N or len(sb) != M:
    ok = False
    exit
ans = 1
vacant = 1
for i in range(N*M,0,-1):
    if i in sa and i in sb: continue
    if i in sa:
        vacant = M - bisect.bisect_left(B,i)
    elif i in sb:
        vacant = N - bisect.bisect_left(A,i)
    else:
        x = M - bisect.bisect_left(B,i)
        y = N - bisect.bisect_left(A,i)
        vacant = x*y - (N*M-i)
    if vacant < 0:
        ok = False
        exit
    ans *= vacant
    ans %= MOD
print(ans if ok else 0)   

Measured memory_bytes: 3188
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long X = sc.nextInt();
		int M = sc.nextInt();
		long prev = X, ans = X, x = 0;
		int st = -1, end = -1;
		long[] sum = new long[M+2];
		sum[0] = X;
		List<Long> l = new ArrayList<>();
		Set<Long> s = new HashSet<>();
		l.add(X);
		s.add(X);
		for(int i = 1; i < N; i++) {
			long mod = prev * prev % M;
			ans += mod;
			sum[i] = sum[i-1] + mod;
			if(!s.contains(mod)) {
				s.add(mod);
				l.add(mod);
			}
			else {
				x = mod;
				end = i;
				st = l.indexOf(mod);
				break;
			}
			prev = mod;
		}
		int T = end - st;
		if(end != -1 && end < N) {
			ans = (N - st) / T * (sum[end] - sum[st]);
			if(st != 0)
				ans += sum[st-1];
			if((N - st) % T != 0) {
				ans += sum[(int)((N - st) % T - 1) + st];
				if(st != 0)
					ans -= sum[st-1];
			}
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 44396
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<math.h>
#include<tuple>
#include<string.h>
#include <numeric> 
#include<unordered_map>
using namespace std; 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define pp(...) "\033[94m [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define pp1(...) "\033[1;47;35m" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "]\033[0m"
#define dg(x) debug() << pp1(x)
#define dg1(x) debug() << "[line : " << __LINE__ <<"]"<< pp(x)
#define dg2(x,y) debug() << "[line : " << __LINE__ <<"]"<< pp(x) pp(y)
#define dg3(x,y,z) debug() << "[line : " << __LINE__ <<"]"<< pp(x) pp(y) pp(z)
#define dg4(w,x,y,z) debug() << "[line : " << __LINE__ <<"]"<< pp(w) pp(x) pp(y) pp(z)
template<typename T> void db(T x ){ debug() <<">>> " <<  x; }
template<typename T> void db(T x , T y){ debug() <<">>> " <<  x <<" , "<< y; }
template<typename T> void db(T x , T y , T z){ debug() <<">>> "<< x <<" , "<< y <<" , "<< z; }
template<typename T> void db(T x , T y , T z , T a){ debug() <<">>> "<< x <<" , " << y <<" , "<< z <<" , "<< a; }
#define int long long
#define all(x) x.begin() , x.end()
#define clr(x , y) memset(x , y , sizeof x);
#define sz(x) (int)x.size()

const int Mod = 1e9 + 7;
const int inf = 1e18;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;
  vector<vector<int>> a (N , vector<int>(3));
  for(int i = 0; i < N; i++) {
    cin >> a[i][0] >> a[i][1] >> a[i][2];
  } 
  auto cal = [&](vector<int> &data) {
    int ans = 0;
    for(int i = 0; i < M; i++) {
      ans += data[i];
    }
    return ans;
  };
  int ans = 0;
  for(int mask = 0; mask < 8; mask++) {
    vector<int> tmp;
     for(int i = 0; i < N; i++) {
       int sum = 0;
       for(int j = 0;j < 3; j++) {
         if(mask & (1 << j)) {
           sum += a[i][j];
         }else sum -= a[i][j];
       }
       tmp.push_back(sum);
       sort(tmp.rbegin() , tmp.rend());
     }
     ans = max(ans , cal(tmp));
  }
  cout << ans << '\n';
}

Measured memory_bytes: 3712
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int A = scan.nextInt();
		int B = scan.nextInt();

		double ave = (A + B) / 2.0;

		System.out.println((int) Math.ceil(ave));
	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 27048
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
	char a[10010];
	int n;
	gets(a);
	n=strlen(a);
	for(int i=0;i<n;i++){
		if(a[i]=='a' or a[i]=='e' or a[i]=='i' or a[i]=='o' or a[i]=='u'){
			printf("vowel");
		}else{
			printf("consonant");
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
	int a,b,c;
	int flag = 0;
	scanf("%d%d%d",&a,&b,&c);
	for(int i = 1; i <= 1e5; i++){
		if(i*a%b == c){
			flag = 1;break;
		}
	}
	if(flag) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#080_C
n=int(input())
f=[list(map(int,input().split())) for _ in range(n)]
p=[list(map(int,input().split())) for _ in range(n)]
ans=-10**9

for i in range(1,2**10):
    l=[]
    for j in range(10):
        if (i>>j)&1:
            l.append(1)
        else:
            l.append(0)
    res=0       
    for j in range(n):
        res+=p[j][sum([f[j][k]*l[k] for k in range(10)])]
    ans=max(ans,res)
    
print(ans)

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

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

    if(a==b && b == c)
        ans = 1;
    else if(a == b || b == c || c == a)
        ans = 2;
    else
        ans = 3;

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


Measured memory_bytes: 256
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=25;
const char t[]={" YAKI"};
char s[N];int n;
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	if(n<4)return puts("No"),0;
	fp(i,1,4)if(s[i]!=t[i])return puts("No"),0;
	puts("Yes");
	return 0;
}

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

int main() {
 int N,K;
  cin >> N >> K;
  vector<int> p(N);
  for(int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  sort(p.begin(),p.end());
  int sum = 0;
  for (int i = 0; i < K; i++){
 sum += p.at(i);
  }
  cout << sum << endl;
  }


Measured memory_bytes: 3616
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = {A[i][0] for i in range(N)}
match = 0

while candidate:
    day += 1
    used = set()
    next = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if A[b-1][0] == (b, a):
            match += 1
            A[a-1].popleft()
            A[b-1].popleft()
            if A[a-1]:                
                next.add(A[a-1][0])
            if A[b-1]:
                next.add(A[b-1][0])
            used.add(a)
            used.add(b)
    if match == N * (N-1) // 2:
        break
    candidate = next
    if not used:
        print(-1); exit()

print(day)
#


Measured memory_bytes: 83548
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;
int main(){
    ll n,q;
    string s;
    cin>>n>>q>>s;
    vector<ll>l(q),r(q);
    for(int i=0;i<q;i++){
        ll li,ri;
        cin>>li>>ri;
        l[i]=li-1;
        r[i]=ri-1;
    }
    vector<ll>dp(n);
    dp[0]=0;
    for(ll i=1;i<dp.size();i++){
        ll cnt=0;
        if("AC"==s.substr(i-1,2)){
            cnt=1;
        }
        dp[i]=cnt+dp[i-1];
    }
    for(ll i=0;i<q;i++){
        cout<<dp[r[i]]-dp[l[i]]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3456
N = int(input())
LR = [[0,0] for _ in range(N)]
for i in range(N):
  a,b = map(int, input().split())
  LR[i] = [a-b,a+b]

LR.sort(key=lambda x: x[0])
# print(LR)
prev_right = - 10**9 #一つ前の右端
cnt = 0
for i in range(N):
  if LR[i][0]>=prev_right: #次の左端が前の右端以上なら
    cnt += 1
    prev_right = LR[i][1]
  else:
    if LR[i][1]<prev_right:
      prev_right = LR[i][1]
  # print(prev_right)

print(cnt)

Measured memory_bytes: 21388