akhauriyash/Code-Regression huggingface dataset:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc *bufio.Scanner
var out *bufio.Writer

func main() {
	sc = bufio.NewScanner(os.Stdin)
	//bytes, _ := ioutil.ReadFile("./stdin.txt")
	//sc = bufio.NewScanner(strings.NewReader(string(bytes)))
	out = bufio.NewWriter(os.Stdout)
	buf := make([]byte, 1<<20)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush()

	n := nextInt()
	idx := make([]int, n)
	p, q := intArrayToString(nextInts(n)), intArrayToString(nextInts(n))
	for i := 0; i < n; i++ {
		idx[i] = i
	}
	perm := permute(idx)
	sp := make([]string, len(perm))
	for i := 0; i < len(sp); i++ {
		for j := 0; j < len(perm[i]); j++ {
			perm[i][j]++
		}
		sp[i] = intArrayToString(perm[i])
	}
	sort.Sort(sort.StringSlice(sp))

	a, b := 0, 0
	for i := 0; i < len(sp); i++ {
		if sp[i] == p {
			a = i
		}
		if sp[i] == q {
			b = i
		}
	}
	if a > b {
		a, b = b, a
	}

	fmt.Fprintln(out, b-a)
}

func intArrayToString(arr []int) string {
	c := make([]byte, len(arr))
	for i := 0; i < len(arr); i++ {
		c[i] = byte(arr[i]) + '0'
	}
	return string(c)
}

func permute(nums []int) [][]int {
	ret := make([][]int, 0, factorial(len(nums)))
	ret = append(ret, append([]int{}, nums...))

	n := len(nums)
	p := make([]int, n+1)
	for i := 0; i < n+1; i++ {
		p[i] = i
	}
	for i := 1; i < n; {
		p[i]--
		j := 0
		if i%2 == 1 {
			j = p[i]
		}

		nums[i], nums[j] = nums[j], nums[i]
		ret = append(ret, append([]int{}, nums...))
		for i = 1; p[i] == 0; i++ {
			p[i] = i
		}
	}
	return ret
}

func factorial(n int) int {
	ret := 1
	for i := 2; i <= n; i++ {
		ret *= i
	}
	return ret
}

func next() string {
	sc.Scan()
	return sc.Text()
}
func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}
func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func intMin(a, b int) int {
	if a > b {
		return b
	}
	return a
}
func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 6880
{-#LANGUAGE FlexibleContexts#-}
import Control.Monad
import Control.Monad.State
import Control.Monad.Reader
import Control.Arrow
-- import Control.Comonad
import Data.Maybe
import Data.List
import Data.Bool
import Data.Fixed
import Data.Tuple
import Data.Ratio
import qualified Data.Map.Strict as M
import qualified Data.Array.IO as IA
import qualified Data.Vector as V

getI = read <$> getLine :: IO Int
getIs = map read . words <$> getLine :: IO [Int]
getD = read <$> getLine :: IO Double
getDs = map read . words <$> getLine :: IO [Double]
getInt = read <$> getLine :: IO Integer
getInts = map read . words <$> getLine :: IO [Integer]

type Row = Integer
type Col = Integer
type PointI = (Integer, Integer)
type Point = (Int, Int)

mmm = 1000000007
fact n
    | n < 1 = 1
    | True = foldr1 (*) [1..n]
ti = toInteger
fi = fromInteger
fig = fromIntegral
rf = realToFrac

(.<.) :: Integer -> Integer -> Integer
(.<.) f g -- combination
    | g < 1 || f < 1 || f < g = 1
    | True = foldr1 (*) (take (fi g) [f,f-1..]) `div` fact g
(.>.) f g --combination with repetition
    | g < 1 || f < 1 = 1
    | True = fact (f + g - 1) `div` (fact (f - 1) * fact g)
comb = (.<.)
combWp = (.>.)

unique a = unique_ (reverse . sort $ a) [] Nothing
    where
        unique_ [] arr _ = arr
        unique_ (x:xs) arr n
            | n == Just x = unique_ xs arr n
            | otherwise = unique_ xs (x:arr) $ Just x
 
zeroume keta num
    | (length . show $ num) > keta = show num
    | otherwise = do 
        let zeros = take keta $ repeat '0'
        reverse . take keta $ (reverse . show $ num) ++ zeros
 
i2b num
    | num < 2 = show num
    | otherwise = i2b_ num []
        where
            i2b_ num str
                | num == 0 = str
                | num == 1 = '1':str
                | otherwise = do
                    let next = num `div` 2
                    let this = if odd num then '1' else '0'
                    i2b_ next (this:str)

mapIncr = mapPlus 1
mapPlus n Nothing = Just n
mapPlus n a = (+) n <$> a

countIf f = length . filter f

enumDivisor :: Int -> [Int]
enumDivisor n = do
    let sqrted = floor $ sqrt (fromIntegral n)
        smaller = filter (\x -> mod n x == 0) [1..sqrted]
        bigger = reverse $ map (div n) smaller
    if head bigger == sqrted then smaller ++ (init bigger)
    else smaller ++ bigger

safeHead [] = Nothing
safeHead (x:_) = Just x

-- 
--
--

main = all (flip elem "aiueo") <$> getLine >>= putStrLn . bool "consonant" "vowel"


Measured memory_bytes: 380
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    int n, m, x, y;
    bool ck = false;
    cin >> n >> m >> x >> y;
    int anmax = -110, bmmin = 110;
    vector<int>an(n);
    vector<int>bm(m);
    for(int i = 0; i < n; i++){
        cin >> an.at(i);
        anmax = max(anmax, an.at(i));
    }
    for(int i = 0; i < m; i++){
        cin >> bm.at(i);
        bmmin = min(bmmin, bm.at(i));
    }
    dump(anmax);
    dump(bmmin);
    if(x < bmmin && bmmin <= y && anmax < bmmin){
        ck = true;
    }
    if(ck){
        cout << "No War" << endl;
    }
    else{
        cout << "War" << endl;
    }
    solve();
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int T;
  T=1;
  while(T--)
  {
    int n;
    cin>>n;
    vector<vector<int> > a(n,vector<int> (3));
    vector<vector<int> > dp(n,vector<int> (3));
    for(int i=0;i<n;i++)
    {
      for(int j=0;j<3;j++)
      {
        cin>>a[i][j];
      }
    }
    //cout<<"E"<<endl;
     for(int i=0;i<3;i++)
    {
      dp[0][i]=a[0][i];
    }
    for(int i=1;i<n;i++)
    {
      for(int j=0;j<3;j++)
      {
        dp[i][j]=max(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+a[i][j];
      }
    }
   // cout<<"F"<<endl;
    int ans=max(dp[n-1][0],dp[n-1][1]);
    ans=max(ans,dp[n-1][2]);
    cout<<ans<<endl;
  }
}


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

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    string S;
    cin >> S;
    int f = 0, l = S.length() - 1;
    int ans = 0;
    while (f <= l)
    {
        if (S[f] == S[l])
        {
            f++;
            l--;
            continue;
        }
        if (S[f] == 'x')
        {
            f++;
            ans++;
            continue;
        }
        else if (S[l] == 'x')
        {
            l--;
            ans++;
            continue;
        }
        ans = -1;
        break;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (ll i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (ll i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,x) for (ll i = 0; i < x.size(); i++)
#define RREPALL(i,x) for (ll i = x.size()-1; i >= 0; i--)
#define REPITR(itr,x) for (auto itr = (x).begin(); itr != (x).end(); itr++)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))
#define MIN_ELEMENT(x) min_element(ALL(x))
#define MAX_ELEMENT(x) max_element(ALL(x))
#define COUNT(x,num) count(ALL(x), num)
#define MEMSET(x,val) memset(x, val, sizeof(x))
#define CHMAX(a,b) a = max(a,b)
#define CHMIN(a,b) a = min(a,b)
#define debug(x) cerr<<__LINE__<<": "<<(#x)<<" = "<<(x)<<endl;
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
#define e1 first
#define e2 second
#define newline putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef vector<ll> VLL;
typedef vector<vector<ll>> VVLL;
const int INF = 1e7;
const ll MOD = 1e9 + 7;
const double pi = 3.141592653589793;
const VI dx = {1, 0, -1, 0};
const VI dy = {0, 1, 0, -1};

int main()
{
    char n;
    cin>>n;
    cout<<(isupper(n) ? 'A' : 'a')<<endl;

    return 0;
}


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

using namespace std;

int main() {
  int a, b, m;
  cin >> a >> b >> m;
  vector<int> as(a);
  vector<int> bs(b);
  for (auto &v : as)
    cin >> v;
  for (auto &v : bs)
    cin >> v;

  int ans =
      *min_element(as.begin(), as.end()) + *min_element(bs.begin(), bs.end());

  for (int i = 0 ; i < m; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    ans = min(as[x-1] + bs[y-1] - c, ans);
  }

  cout << max(0, ans) << endl;

}


Measured memory_bytes: 4064
#include <bits/stdc++.h>
using namespace std;
const int infty = (int)((1LL << 31) - 1);
struct segment_tree {
  public:
    int n, N;
    vector<long long> tr, lz;
    segment_tree (vector<int> v) {
      n = v.size();
      N = 1;
      while (N < n) N <<= 1;
      tr.resize(2 * N);
      lz.resize(2 * N, 0);
      for (int i = 0; i < n; i++) tr[N + i] = v[i];
      for (int i = N - 1; i >= 1; i--) tr[i] = tr[2 * i] + tr[2 * i + 1];
    }
    inline void pg (int k, int L, int R) {
      if (lz[k]) {
        if (k < N) {
          lz[2 * k] += lz[k] >> 1;
          lz[2 * k + 1] += lz[k] >> 1;
        }
        tr[k] += lz[k];
        lz[k] = 0;
      }
    }
    void add (int l, int r, int x, int k = 1, int L = 0, int R = -1) {
      if (R == -1) R = N;
      pg(k, L, R);
      if (r <= L || R <= l) {
        return;
      } else if (l <= L && R <= r) {
        lz[k] += x * (R - L);
        pg(k, L, R);
      } else {
        int C = (L + R) / 2;
        add(l, r, x, 2 * k, L, C);
        add(l, r, x, 2 * k + 1, C, R);
        tr[k] = tr[2 * k] + tr[2 * k + 1];
      }
    }
    long long getSum (int l, int r, int k = 1, int L = 0, int R = -1) {
      if (R == -1) R = N;
      pg(k, L, R);
      if (r <= L || R <= l) {
        return 0;
      } else if (l <= L && R <= r) {
        return tr[k];
      } else {
        int C = (L + R) / 2;
        return getSum(l, r, 2 * k, L, C) + getSum(l, r, 2 * k + 1, C, R);
      }
    }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  segment_tree sgt(vector<int>(n, 0));
  while (q--) {
    int c;
    cin >> c;
    if (c == 0) {
      int s, t, x;
      cin >> s >> t >> x;
      sgt.add(--s, t, x);
    } else {
      int s, t;
      cin >> s >> t;
      long long ret = sgt.getSum(--s, t);
      cout << ret << '\n';
    }
  }
  return 0;
}


Measured memory_bytes: 7336
#include <stdio.h>
int main()
{
	char x;
	char y[1001];
	int sum=0;
	int num,i=0;

	while(1){
		scanf("%s",y);
		//printf("%c\n",x);
  		if(y[0]=='0')break;
  		//if(x!="\n")
  		sum=0;
  	 for(i=0;y[i]!='\0';i++){
  	        num=y[i]-'0';
		    sum += num;
		    //sum += y[i]
		    //printf("%d\n",sum);
		    //printf("%d\n",i);
	}
  	    printf("%d\n",sum);
		//printf("%d\n",sum);
	//printf("%d\n",sum);
	}
	return 0;
}


Measured memory_bytes: 2092
#include <iostream>
#define int long long
using namespace std;

signed main() {
	int n, b, a, box, zan, ans;
	
	cin>>n >>a >>b;
	box = n/(a+b);
	zan = n-box*(a+b);
	
	if(a-zan >= 0){
		ans = a*box+zan;
	}
	else {
		ans = box*a+a;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

ll mod_pow(ll x,ll n){
  ll res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n/=2;
  }
  return res;
}

int n, cnt[100005];

signed main(){
  
  cin>>n;
  
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    cnt[a]++;
  }
  
  if( n % 2 ){
    
    if( cnt[0] != 1 ){
      cout<<0<<endl;
      return 0;
    }
    
    int x = 2, flag = 1;
    
    for(int i=1;i<n/2+1;i++){
      
      if( cnt[x] != 2 ) flag = 0;
      
      x += 2;
      
    }
    
    if( !flag ){
      cout<<0<<endl;
      return 0;
    }
    
    cout<<mod_pow(2,n/2)<<endl;
    
  }else{
    
    int x = 1, flag = 1;
    
    for(int i=1;i<n/2;i++){
      
      if( cnt[x] != 2 ) flag = 0;
      
      x += 2;
      
    }
    
    if( !flag ){
      cout<<0<<endl;
      return 0;
    }
    
    cout<<mod_pow(2,n/2)<<endl;
    
  }
  
  
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int D;
    cin >> D;
    vector<int>c(26);
    for(int i = 0; i < 26; i++) {
        cin >> c[i];
    }
    vector<vector<int>>s(D,vector<int>(26));
    for(int i = 0; i < D; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    vector<int>t(D);
    for(int i = 0; i < D; i++) {
        t[i] = rand()%26+1;
    }
    int ans = 0;
    vector<int>Last(26);
    for(int i = 0; i < D; i++) {
        ans+=s[i][t[i]-1];
        Last[t[i]-1] = i+1;
        for(int j = 0; j < 26; j++) {
            ans-=c[j]*(i+1-Last[j]);
        }
    }
    int M = 777777;
    for(int i = 0; i < M; i++) {
        int d = rand()%D+1;
        int q = rand()%26+1;
        int ord = ans;
        int X = 0;
        int Y = 0;
        int A = 0;
        int B = 0;
        ans+=s[d-1][q-1]-s[d-1][t[d-1]-1];
        for(int j = 0; j < D; j++) {
            if(t[j] == t[d-1]) {
                if(j == d-1) {
                    Y = j+1;
                }
                else {
                    X = j+1;
                }
                A = j+1;
            }
            if(t[j] == q) {
                Y = j+1;
                B = j+1;
            }
            ans-=c[t[d-1]-1]*(j+1-X)-c[t[d-1]-1]*(j+1-A);
            ans+=c[q-1]*(j+1-B)-c[q-1]*(j+1-Y);
        }
        if(ans > ord) {
            ord = ans;
            t[d-1] = q;
        }
        else {
            ans = ord;
        }
    }
    for(int i = 0; i < D; i++) {
        cout << t[i] << endl;
    }
}

Measured memory_bytes: 3716
import math
n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]

def dist(a, b):
    return math.sqrt(sum([(a[i] - b[i])**2 for i in range(d)]))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        y = x[i]
        z = x[j]
        w = dist(y, z)
        # print(w, int(w), w == int(w))
        if w == int(w):
            ans += 1

# print(x)
print(ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;
constexpr long long int INF = std::numeric_limits<long long int>::max();
constexpr long long int NINF = std::numeric_limits<long long int>::min();
#define int long long int

void solve() {
  int N, M;
  cin >> N >> M;
  vector<bool> A(N + 1, false);
  vector<bool> B(N + 1, false);

  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
      A[b] = true;
    } else if (b == N) {
      B[a] = true;
    }
  }

  for (int i = 0; i < A.size(); i++) {
    if (A[i] && B[i]) {
      cout << "POSSIBLE" << endl;
      return;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
	int A, B;
	string S;
	cin >> A >> B;
	cin >> S;
	for (int i = 0; i < A; ++i) {
		if (!('0' <= S[i] && S[i] <= '9')) {
			cout << "No";
			return 0;
		}
	}
	if (S[A] != '-') {
		cout << "No";
		return 0;
	}
	for (int i = A + 1; i < A + B + 1; ++i) {
		if (!('0' <= S[i] && S[i] <= '9')) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def f(n):
    res = 0
    if n == 0:
        return 0
    else:
        if n % 2 == 0:
            res = n
            n -= 1
        res = res ^ (((n + 1) // 2) % 2)
    return res


def main():
    a, b = input_int_list()
    # f(A,B) = f(0,a-1) XOR f(0,b)
    # n が偶数のとき、n XOR n+1 = 1

    if a == 0:
        print(f(b))
        return
    else:
        print(f(b) ^ f(a - 1))
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 61980
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
using namespace std;

//素数判定
bool IsPrime(int p) {
	if (p == 1) return false;
	for (int i = 2; i < p; i++) {
		if (p%i == 0) return false;
	}
	return true;
}

//10進数の自然数の桁数を返す
int GetDigit(int num) {
	return (int)log10(num) + 1;
}

int main() {
	int N;
	int a[150];
	double dis[150];
	int sum = 0;
	double abe;

	cin >> N;

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

	abe = (double)sum / N;

	//cout << "abe:" << abe << endl;

	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		dis[i] = abs(abe - a[i]);
		//cout << dis[i] << endl;
	}

	for (int i = 1; i < N; i++)
	{
		if (dis[i] < dis[ans]) {
			ans = i;
		}
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int e;
  vector<int> ans;
  while(cin >> e,e){
    vector<int> combi;
    for(int y = 0;e-y*y+y >= 0;y++){
      for(int z = 0;e-y*y+y-z*z*z+z >= 0;z++){
        if(e-y*y-z*z*z >= 0)combi.push_back(e-y*y+y-z*z*z+z);
      }
    }
  int q = 1000000;
  for(int i = 0;i < combi.size();i++)q = min(q,combi[i]);
  ans.push_back(q);
  }
  for(int i = 0;i < ans.size();i++)cout << ans[i] << endl;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h> 
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-6
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 1e4+10;
const int N = 1e6+10;

int n;
int a[maxn];
int num[N];
int prime[N];	//下标从1开始
bool not_prime[N];

int sieve(int n){	//把2到n内所有素数筛选出来 
    int p = 0;
    for (int i = 2; i <= n; ++i){
        if(!not_prime[i])
           prime[++p] = i;
        for(int j = 1; j <= p&&i*prime[j]<=n; j++){
        	not_prime[i*prime[j]] = true;	//把比最小素因子的素数的倍数筛除 
        	if(i%prime[j]==0) break;	//已找到最小素因子	
		}
    }
    return p;   //  返回素数个数
}

void pri_fac(ll x){
	for(int i=1;prime[i]*prime[i]<=x;i++){
		int y =prime[i];
		if(x%y==0){
			int p=0;
			while(x%y==0){
				x/=y;
				p++;
			}
			num[y] = max(p,num[y]);
		}
	}
	if(x>1) num[x] = max(1,num[x]);
}

ll	qpow(ll n,ll b){
	ll res=1;
	while(b){
		if(b&1) res = res*n%mods;
		n=n*n%mods;
		b>>=1;
	} 
	return res;
}

int main() {
	scanf("%d",&n);
	int maa=0;
	sieve(N);
	F(i,1,n){
		scanf("%d",&a[i]);
		//a[i] = rand()%1000000+1;
		maa = max(a[i],maa); 
		pri_fac(a[i]);
	}
	ll sum=1;
	F(i,1,maa){
		sum=sum*qpow(i,num[i])%mods;
	}
	int ans = 0;
	F(i,1,n){
		ans = (ans+qpow(a[i],mods-2))%mods;
	}
	ans=ans*sum%mods;
	printf("%d\n",ans);
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
struct point{
    ll x, y;
    bool operator ==(const point &a) const{
        return a.x == x && a.y == y;
    }
    point operator +(const point &a){
        return {x+a.x, y+a.y};
    }
    point operator -(const point &a){
        return {x-a.x, y-a.y};
    }
};
 
point nista;
 
ll dist(point g){
    return g.x*g.x + g.y*g.y;
}
 
int quadrant(point a){
    if(a.x > 0 && a.y >= 0) return 1;
    if(a.x <= 0 && a.y > 0) return 2;
    if(a.x < 0 && a.y <= 0) return 3;
    return 4;
}
 
ll cross(point base, point a, point b){
    a.x -= base.x;
    a.y -= base.y;
    b.x -= base.x;
    b.y -= base.y;
    return a.x*b.y - a.y*b.x;
}
 
bool cmp(point a, point b){
    if(quadrant(a) == quadrant(b)){
        return cross(nista, a, b) > 0;
    }
    return quadrant(a) < quadrant(b);
}
 
point a[400005];
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
    
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i].x >> a[i].y;
        if(a[i].x == 0 && a[i].y == 0){
            n--, i--;
        }
    }
    nista.x = 0;
    nista.y = 0;
    sort(a+1, a+1+n, cmp);
    for(int i=1; i<n; i++){
        if(cross(nista, a[i], a[i+1]) == 0 && a[i].x*a[i+1].x >= 0 && a[i].y*a[i+1].y >= 0){
            a[i+1] = a[i+1] + a[i];
            a[i] = nista;
        }
    }
    int gde = 0;
    for(int i=1; i<=n; i++){
        if(!(a[i] == nista)) a[++gde] = a[i];
    }
    n = gde;
    //cout << n << endl;
    for(int i=n+1; i<=2*n; i++){
        a[i] = a[i-n];
    }
    int j = 0;
    point sum = {0, 0};
    ll res = 0;
    for(int i=1; i<=n; i++){
        sum = sum - a[i-1];
        res = max(res, dist(sum));
        while((j < i) || (j < i+n-1 && (cross(a[i], nista, a[j+1]) < 0 || a[j+1] == a[i]))){
            j++;
            sum = sum + a[j];
            res = max(res, dist(sum));
        }
        res = max(res, dist(sum));
    }
    cout << sqrtl(1.0*res);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define fill(x,y) memset(x,y,sizeof(x))
#define name(x) #x
using namespace std;


const int INF = INT_MAX;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

map<ll,ll> dp;

ll filldp(ll n){
    
    if (dp.count(n)) return dp[n];

    ll res = (filldp(n/2) + filldp((n-1)/2)) %MOD;
    res = (res + filldp((n-2)/2)) %MOD;
    
    dp[n] = res;
    return res;
    
}


int main() {
    ll N;
    cin >> N;
    
    dp[0] = 1;
    dp[1] = 2;
    
    ll res = filldp(N);
    
    cout << res << endl;
    
    return 0;
}




Measured memory_bytes: 256
x,n = map(int, input().split())
valid = [1] *101
p = list(map(int, input().split()))
for i in range(n):
	valid[p[i]] = 0

#print(valid)

for j in range(100):
#	print(x,j,x-j,x+j)
#	print(valid[x-j])
#	print(valid[x+j])
	if((x-j) >= 1):
		if(valid[x-j] == 1):
			print(x-j)
			break
	else:
		print(0)
		break
	if((x+j) <= 100):
#		print("aaa")
		if(valid[x+j] == 1):
			print(x+j)
			break
	else:
		print(101)
		break


Measured memory_bytes: 61972
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <cmath>
#include <complex>
#include <algorithm>
#include <utility>
#include <regex>
#include <cstdint>
#include <numeric>
#include <functional>
#include <cassert>

using namespace std;
using ll = int64_t;
using ull = uint64_t;

constexpr ll INF = 1'000'000'000'000'000'000;
namespace utils{
    template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;
    template<class T> using min_queue = p_queue<T, greater<T>>;
    template<class T> using max_queue = p_queue<T, less<T>>;

    template<class T> bool min_update(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }
    template<class T> bool max_update(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }
    using V_Set = unordered_set<int>;
    using E_Set = unordered_map<int, V_Set>;

#define ALL(x) begin(x), end(x)
#define rALL(x) rbegin(x), rend(x)
}
using namespace utils;


void sub_main(istream &is) {
    ll N;
    is >> N;
    if(!is) return;
    int difc = 0;
    for (int i = 1; i <= N; ++i) {
        int t;
        is >> t;
        difc += t != i;
    } // end i
    cout << (difc <= 2 ? "YES" : "NO") << endl;

}

int main(int argc, char *argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(16) << scientific;
#ifdef DEBUG
    string test_cases = "test_B.txt";
    cerr << "DEBUG MODE" <<  endl;
    cerr << test_cases << " -->" << endl;
    auto fs = fstream(test_cases, fstream::in);
    int lp = 0;
    while(fs) {
        lp++;
        cout << lp <<  "#------\n";
        sub_main(fs);
    }
    cout << "------#" << endl;
    if(lp <= 1) sub_main(cin);
#else
    sub_main(cin);
#endif
    return 0;
}


Measured memory_bytes: 256
#3問目
import itertools
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N, P = map(int, input().split())
A = list(map(int, input().split()))
#偶数グループと奇数グループにわける
odd = []
even = []
c = 0
for i in A:
    if i % 2 == 0:
        even.append(i)
    else:
        odd.append(i)
#奇数グループは組み合わせの総数を出す
#もしP=1なら奇数グループから奇数個を出す組み合わせの数、P=0なら奇数グループから偶数個を出す組み合わせの数
if P == 1:
    #奇数グループから奇数個を出す組み合わせの数
    for i in range(1, len(odd)+1, 2):
        c += combinations_count(len(odd), i)
if P == 0:
    #奇数グループから偶数個を出す組み合わせの数
    for i in range(0, len(odd)+1, 2):
        c += combinations_count(len(odd), i)
        
print(2 ** len(even) * c) 

Measured memory_bytes: 3064
S = input()
M = ["01", "02", "03", "04", "05", "06", "07", "08", "09", "10", "11", "12"]

f = False
f2 = False
if (S[2:] in M): f = True
if (S[:2] in M): f2 = True

if f and f2:
    print ("AMBIGUOUS")
elif f:
    print ("YYMM")
elif f2:
    print ("MMYY")
else:
    print ("NA")


Measured memory_bytes: 3060
x,y,z,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
b=sorted(list(map(int,input().split())),reverse=True)
c=sorted(list(map(int,input().split())),reverse=True)
ab=[]
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort(reverse=True)
ans=[]
for i in range(min(k,x*y)):
    for j in range(z):
        ans.append(ab[i]+c[j])
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

Measured memory_bytes: 222956
n, k = map(int, input().split())
nList = [0 for _ in range(n)]
for i in range(k):
    d = int(input())
    aList = list(map(int, input().split()))
    for j in aList:
        nList[j-1] += 1
cnt = 0
for i in nList:
    if i == 0:
        cnt += 1
print(cnt)


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

const int Nmax=200010;
//#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//#definr REP(i,n) FOR(i,0,n)
//#define dump(x) cout << #x << "=" << (x) << endl;
//#define debug(x) cout << #x << "=" << (x) << "(L" << _LINE_ << ")" << "" << _FILE_ << endl;
//ll a[Nmax];
//int* P = new int[N];

int main() {
	int N;
	cin >> N;
	ll X[Nmax],Cl[Nmax];
	for(int i=0;i < N;i++){
		cin >> X[i];
		Cl[i] = X[i];
	}
	sort(Cl, Cl+N);
	ll med1=Cl[N/2],med2=Cl[N/2-1];
	for(int i=0;i < N;i++){
		if(X[i] <= med2) cout << med1 << endl;
		else cout << med2 << endl;
	}

	return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector <int> adj[100009];
bool visited[100009]={0};
map <int,int> mp;
void bfs()
{
    queue <int> q;
    q.push(1);
    visited[1]=1;
    while(!q.empty())
    {
        int par=q.front();
        for(int i:adj[par])
        {
            if(!visited[i])
            {
                q.push(i);

                mp[i]=par;
                visited[i]=1;
            }
        }
        q.pop();

    }


}
int main()
{

    ll n,k;
    cin>>n>>k;

    for(ll i=0;i<k;i++)
    {
        ll a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    bfs();
    if((ll)mp.size()!=(n-1))
        cout<<"No"<<endl;
    else
    {
        cout<<"Yes"<<endl;
        for(ll i=2;i<=n;i++)
            cout<<mp[i]<<endl;
    }
}

Measured memory_bytes: 14656
function main(inputs) {
  var N = inputs.shift();
  var pairs = [];
  for(var i=0;i<N;i++){
    pairs.push([inputs.shift(), inputs.shift()]);
  }

  var BTC = 380000.0;
  var ans = 0;
  pairs.forEach(function(v){
    if(v[1] == 'BTC'){
      ans += BTC*v[0];
    }else{
      ans += Number(v[0]);
    }
  })
  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/));


Measured memory_bytes: 7372
#include <iostream>
#include <math.h>
#include <string>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
	int n, m, a[1000], sum = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		sum += a[i];
	}
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i]*4*m >= sum)
		{
			count++;
		}
	}
	if (count >= m)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

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

    ll X;
    cin >> X;

    cout << lcm(360, X) / X << "\n";
}

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

int main() {
	
	long long int n,sum=0; cin>>n;
	int a[n+1],b[n];
	for(int i=0;i<n+1;i++) cin>>a[i];
	for(int i=0;i<n;i++) {
		cin>>b[i];
	}
	for(int i=0;i<n;i++) {
		if(a[i]>=b[i]) { sum+=b[i]; }	//Remove Equal to
		else {
			b[i]-=a[i];
			sum+=a[i];
			if(a[i+1]>=b[i])  { //Remove Equal to
				a[i+1]-=b[i]; 
				sum+=b[i];
			}
			else {
				sum+=a[i+1]; 
				a[i+1]=0;
			}	
		}
	}
	cout<<sum<<endl;
}


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

#define int long long

int clz(int n) {
    if(n%2==0) return n / 2;
    else return n * 3 + 1;
}

signed main() {
    int n;
    while(cin>>n, n!=0) {
        int ans = 0;
        while(n!=1) {
            n = clz(n);
            ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

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

struct Ac
{
    int x,y;
} ac[111];

struct Bc
{
    int x,y;
} bc[111];

int vis[222][222];
int flag[222];
int pri[222];
int n;

bool _find(int i)
{
    int j;
    for(j=1; j<=n; j++)
    {
        if(vis[ac[i].x][bc[j].x]&&!flag[j])
        {
            flag[j]=1;
            if(pri[j]==-1||_find(pri[j]))
            {
                pri[j]=i;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    memset(vis,0,sizeof(vis));
    memset(pri,-1,sizeof(pri));
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&ac[i].x,&ac[i].y);
    }
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&bc[i].x,&bc[i].y);
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(ac[i].x<bc[j].x&&ac[i].y<bc[j].y)
            {
                vis[ac[i].x][bc[j].x]=1;
            }
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        memset(flag,0,sizeof(flag));
        if(_find(i))
            ans+=1;
    }
    printf("%d\n",ans);
    return 0;
}


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

int main()
{
  int r, g, b;
  cin >> r >> g >> b;

  int tmp = 100 * r + 10 * g + b;

  if(tmp %4 == 0)
    cout << "YES";
  else
  {
    cout << "NO";
  }


}


Measured memory_bytes: 3580
N = int(input())
l = list(map(int,input().split()))
a = 0
judge = True
while True:
    for i in range(N):
        if l[i] % 2 == 0:
            l[i] = l[i] / 2
        else:
            judge = False
            break
    if judge == True:
        a = a + 1
    else:
        break
print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
    
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define $ ios::sync_with_stdio(0);
//#define int long long int
    
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ii = pair<int, int>;
using vi = vector<int>;
using graph = vector<vi>;
using ordered_mset = tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update>;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
//const ll INFLL = (ll)1e17;
const int MAXN = 3123;
const double pi = 3.14159265359;
const double eps = 0.00000001;
 
double p[MAXN];
double dp[MAXN][MAXN];
 
int main() {
    $
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = dp[i - 1][0] * (1 - p[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i][j] = dp[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]);
        }
    }
    double ans = 0;
    for (int i = n/2+1; i <= n; ++i) {
        ans += dp[n][i];
    }
    cout << fixed;
    cout.precision(10);
    cout << ans << '\n';
}

Measured memory_bytes: 72448
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 10005;

int n, m;
string memo[N];
vector <int> dig;
vector <int> cost{0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

bool operator>(const string &a, const string &b) {
  if (a.size() != b.size()) return a.size() > b.size();
  for (int i = 0; i < a.size(); i++) {
    if (a[i] != b[i]) return a[i] > b[i];
  }
  return 0;
}

string go(int x) {
  if (x < 0) return "0";
  if (x == 0) return "";
  if (memo[x] != "-") return memo[x];
  string ans = "0";
  for (int i = 0; i < dig.size(); i++) {
    string add;
    add = (char) (dig[i] + '0');
    string here = go(x - cost[dig[i]]);
    if (x >= cost[dig[i]] && here.back() != '0') {
      if (add + go(x - cost[dig[i]]) > ans) {
        ans = add + go(x - cost[dig[i]]);
      }
    }
  }
  if (ans == "0") return "0";
  return memo[x] = ans;
}

int main() {
  for (int i = 0; i < N; i++) memo[i] = "-";
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    dig.push_back(x);
  }
  cout << go(n) << endl;
  return 0;
}


Measured memory_bytes: 44672
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int main(void){
    int l, i=0, a[10], answer;
    while(2 > i){
        cin >> a[i];
        i++;
    }
    if (a[1] == 100) {
        answer = (std::pow(100, a[0]) * (a[1] + 1));
    } else {
        answer = (std::pow(100, a[0]) * a[1]);
    }
    cout << to_string(answer) << endl;
}

Measured memory_bytes: 3868
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
int hoge(int a){
  ll ret=0;
  while(a>0){ret++;a/=10;}
  return ret;
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e;
  string s,ss,sss;
  cin>>a;
  ll ans=0;
  for(int i=1;i<=a;i++){
    ans+=hoge(i)%2;
  }
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;
const long double eps = 1E-14;

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

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

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

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

string op(string s, ll x) {
	ll N = s.size();
	string t(N,'.');
	rep(i, N - x)t[i] = s[i + x];
	rep(i, x)t[N - x + i] = s[N - 1 - i];

	//cout << t << endl;
	return t;
}

int main() {
	ll N, K;
	string S;
	cin >> N >> K >> S;

	char top = 'z';
	rep(i, N) top = min(top, S[i]);

	string ans = S;

	rep(i, N+1) {
		string T = op(S, i);

		rep(k, min(K,30)-1) {
			ll x = 0;
			for (ll j = N ; j >= 1; j--) {
				if (T[j - 1] != top) { x = j; break; }
			}
			//cout << x << endl;

			if (x == 0) { break; }
			T = op(T, N-x);
		}

		reverse(T.begin(), T.end());
		ans = min(ans, T);
	}

	cout << ans << endl;
}

Measured memory_bytes: 3640
#include <cstdlib>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100005
#define pb push_back
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const double PI  =3.141592653589793238463;
long long MOD = 1000000007;

int stringToInteger(string x){
    int gg=0;
    //stringstream geek(x);
    //geek >> gg;
    return gg;
}

ll powmod(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0){ if(b%2)
        {ans*=a; ans%=m;}
         b/=2; a=a*a; a=a%m;
        }
        return ans%m;
}
ll gcd(ll a,ll b)
{

    return __gcd(a,b);
}
ll mulmod(ll a,ll b,ll m)
{  ll ans=0;
    a %=m;
    while (b>0)
    {       if(b&1) ans = (ans + a) % m;
        a = (a * 2)%m;
        b /= 2;
    }
    return ans % m;
}

ll pow(ll a, ll b, ll MOD)
{
 ll x=1,y=a;
 while(b > 0)
 	{
 		if(b%2 == 1)
 	{
 		x=(x*y);
 		if(x>MOD) x%=MOD;
 	}
 	y = (y*y);
 	if(y>MOD) y%=MOD;
 	b /= 2;
 	}
 return x;
}
ll modInverse(ll a, ll m)
{
    a = a%m;
    for (int x=1; x<m; x++)
       if ((a*x) % m == 1)
          return x;
}
ll maxDivide(ll a, ll b)
{
  while (a%b == 0)
   a = a/b;
  return a;
}
  set<ll>ans;
void primeFactors(ll n)
{

    while (n % 2 == 0)
    {
       ans.insert(2);
        n = n/2;
    }

    for (ll i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n % i == 0)
        {
            ans.insert(i);
            n = n/i;
        }
    }

    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        ans.insert(n);
}
ll is(ll no)
{   if(no==1) return 0;
    set<ll>::iterator it;
for(it=ans.begin();it!=ans.end();it++){
  no = maxDivide(no, *it);
  if(no==1) return 1;
//  if()
 // no = maxDivide(no, 3);
 // no = maxDivide(no, 5);
}
//if(no==1) return 1;
//for(it=ans.begin();it!=ans.end();it++){
//if(no==*it) return 1;
//}
  return 0;
}

int comp(string a,string b)
{
    string aa = a.append(b);
    string bb = b.append(a);

    return aa.compare(bb) > 0 ? 1: 0;

}
int main()
{
    //cout<<powmod(2,7,9)<<endl;
int t;
t=1;
while(t--){

       //int n,k;
       int n;
       cin>>n;
       ll a[n],s[n],p[n];
       for(int i=0;i<n;i++) cin>>a[i];
       p[0]=a[0];
       for(int i=1;i<n;i++) p[i]=__gcd(a[i],p[i-1]);
       s[n-1]=a[n-1];
       for(int i=n-2;i>=0;i--) s[i]=__gcd(a[i],s[i+1]);
       ll ans = p[n-1];
       for(int i=0;i<n;i++)
       {   if(i-1>=0&&i+1<n)
       {

           ll aa = __gcd(p[i-1],s[i+1]);
           ans=max(ans,aa);
       }
       else if(i-1<0)
       {

           ans=max(ans,s[i+1]);
       }
       else
        ans=max(ans,p[i-1]);
       }
       cout<<ans<<endl;



}
}




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

#define int long long
#define pb push_back
#define mod 1000000007
#define endl '\n'
#define w(x) int x;cin>>x; while(x-->0)

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void mysol()
{
    int n; cin >> n;
    int arr[n];
    for (int &a : arr)
        cin >> a;
    int dp[n] = {0};
    dp[0] = 0;
    dp[1] = abs(arr[1] - arr[0]);
    for (int i = 2; i < n; i++)
        dp[i] = min(dp[i - 1] + abs(arr[i] - arr[i - 1]), dp[i - 2] + abs(arr[i] - arr[i - 2]));
    cout << dp[n - 1];

}

int32_t main()
{
    //fast();
    // w(t)
    {
        mysol();
    }
    return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S,T,U;
    int A,B;
    
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    
    if(S == U) cout << A-1 << ' ' << B <<endl;
    else cout << A << ' '<< B-1 << endl;
    
    return 0;
}


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

using namespace std;

int main() {
  int input[5];
  for (int input_i = 0; input_i < 5; input_i++)
    cin >> input[input_i];
  sort(input, input+5, greater<int>());
  for (int input_i = 0; input_i < 5; input_i++) {
    cout << input[input_i];
    if (input_i != 4)
      cout << " ";
  }
  cout << endl;
  return 0;
}

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

class Program
{
    public static void Main( )
    {
        var input = Console.ReadLine( ).Split( ).Select( int.Parse ).ToList( );
        int N = input[ 0 ];
        int M = input[ 1 ];
        int X = input[ 2 ];
        var algorisms = new int[ M ];


        List<List<int>> CArows = new List<List<int>>( );
        for ( int i = 0; i < N; i++ )
        {
            CArows.Add( Console.ReadLine( ).Split( ).Select( int.Parse ).ToList( ) );
        }

        int result = Solve( 0, N, X, CArows, 0, algorisms );
        Console.WriteLine( (result==int.MaxValue) ? -1 : result );
    }



    static int Solve( int i, int N, int X, List<List<int>> rows, int price, int[] Algorisms )
    {
        if ( Check( Algorisms, X ) ) return price;
        if ( i >= N ) return int.MaxValue;

        var row = rows[ i ];
        int C = row[ 0 ];
        int[] A = row.Skip( 1 ).ToArray( );

        int used = Solve( i + 1, N, X, rows, price + C, Add( Algorisms, A ) );
        int nonUsed = Solve( i + 1, N, X, rows, price, Algorisms );

        return ( used <= nonUsed ) ? used : nonUsed;
    }


    static int[] Add( int[] baseList, int[] listToAdd )
    {
        var x = baseList.Zip( listToAdd, ( baselist, add ) => new { Base = baselist, Add = add } )
            .Select( item => item.Base + item.Add ).ToArray( );
        return x;
    }

    static bool Check( int[] targetList, int X )
    {
        return targetList.All( x => x >= X );
    }
}


Measured memory_bytes: 32632
#include <bits/stdc++.h>
#include <vector>
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define REPR(i, n) for (int i = n-1; i >= 0; --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTG(a) sort(ALL(a), greater<int>())
#define REVERSE(a) reverse(ALL(a))
#define bit_search(bit, n) REP(bit, 1<<n)
#define bit_check(bit, i) (bit>>i) & 1
#define setpre(n) fixed << setprecision(n)
#define ENDL cout << endl;
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using VP = vector<PII>;
using VI = vector<int>;
using VVI = vector<VI>;
using Vll = vector<ll>;
using VVll = vector<Vll>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
const int INF = 1e9;
const ll mod = 1e9 + 7;

VI memo(1e5 + 5, -1);

int calc(ll b, ll m)
{
    if (b == 0)
    {
        memo[0] = 1;
        return memo[0];
    }
    if (memo[b] != -1) return memo[b];
    int res = 10 * calc(b-1, m) % m;
    return memo[b] = res;
}

int main(){
  string S;
  cin >> S;
  ll len = S.size();
  VVll dp(len, Vll(13, 0));
  REPR(i, len){
    if (i == len - 1){
        if (S.at(i) != '?'){
            REP(j, 13) if (S.at(i)-'0' == j) dp.at(i).at(j) = 1;
        }
        else REP(j, 10) dp.at(i).at(j) = 1;
        continue;
    }
    int tmp = calc(len-i-1, 13);
    REP(j, 13){
        if (S.at(i) == '?'){
            REP(s_i, 10){
                dp.at(i).at(j) += dp.at(i+1).at((13 + j - ((s_i * tmp) % 13)) % 13);
                dp.at(i).at(j) %= mod;
            }
        }
        else{
            dp.at(i).at(j) += dp.at(i+1).at((13 + j - (((S.at(i)-'0') * tmp) % 13)) % 13);
            dp.at(i).at(j) %= mod;
        }
    }
  }
  cout << dp.at(0).at(5) << endl;

  return 0;
}

Measured memory_bytes: 14080