akhauriyash/Code-Regression huggingface dataset:
/*。*/
#include <iostream>
#include<stdio.h>
#include <cmath>
using namespace std;

class saikoro{
public:
    int s1,s2,s3,s4,s5,s6;
    
public:saikoro(int* mas);
    void west();
    void north();
    void east();
    void sauth();
    void kaiten();
    
};
saikoro::saikoro(int* mas){
    s1=mas[0];
    s2=mas[1];
    s3=mas[2];
    s4=mas[3];
    s5=mas[4];
    s6=mas[5];
}
void saikoro::east(){
    int u=s6;
    s6=s3;
    s3=s1;
    s1=s4;
    s4=u;
    
}
void saikoro::north(){
    int u=s6;
    s6=s5;
    s5=s1;
    s1=s2;
    s2=u;
}
void saikoro::west(){
    int u=s6;
    s6=s4;
    s4=s1;
    s1=s3;
    s3=u;
}
void saikoro::sauth(){
    int u=s6;
    s6=s2;
    s2=s1;
    s1=s5;
    s5=u;
}
void saikoro::kaiten(){
    int u=s2;
    s2=s3;
    s3=s5;
    s5=s4;
    s4=u;
}
int main(){
   int  masu[6];
    for(int i=0;i<6;i++){
        cin>>masu[i];
    }
   // saikoro sai(masu);
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        saikoro sai(masu);
        int flag=0;
        for(int j=0;j<4;j++){
            sai.east();
            for(int k=0;k<4;k++){
                sai.sauth();
                for(int g=0;g<4;g++){
                    sai.kaiten();
                if(sai.s1==a&&sai.s2==b){
                    cout<<sai.s3<<endl;
                    flag=1;
                    break;
                }
   
            }
                if (flag==1)break;
        }
            if(flag==1)break;
    }
    
    }

return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define rep(i,n) for(long long i=0; i<n; i++)
#define Rep(i,n) for(long long i=1; i<n; i++)
#define ll long long
#include <math.h>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <vector>


using namespace std;
#define PI acos(-1)

int main(){
    ll a,b,c;
    cin>>a>>b>>c;
   cout<<c<<" "<<a<<" "<<b<<endl;
}



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

int main(void){

    int flg = 0;

    string s;
    cin >> s;
    
    if(s[2] == s[3]){
        if(s[4] == s[5])
            flg = 1;
     }
    

    if(flg ==  1)
    cout << "Yes" << endl;

    else
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
function main()
  
  N = parse(Int,readline())
  
  T = 0
  X = 0
  Y = 0
  
  check = true
  
  for i in 1:N
    
    (t, x, y) = map(x -> parse(Int,x), split(readline()))
    D_t = t - T
    D_x = abs(x - X)
    D_y = abs(y - Y)
    T = t
    X = x
    Y = y
    
    if D_x + D_y > D_t || (D_t - D_x + D_y) % 2 != 0
      check = false
    end
    
  end
  
  if check
    println("Yes")
  else
    println("No")
  end
  
end

main()

Measured memory_bytes: 151296
# include <bits/stdc++.h>
# define ll long long int
# define pb push_back
# define pf push_front
# define mpi make_pair
# define pi pair<ll,ll>
# define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
# define mod 1000000007
# define endl "\n"
using namespace std;
int main()
{
  fast
  ll n,val=0;
  cin>>n;
  vector <ll> v,ans;
  for(ll i=0;i<n-1;i++)
  {
    ll x;
    cin>>x;
    v.pb(x);
  }
  ans.pb(v[0]);
  for(ll i=0;i<n-2;i++)
  {
    ans.pb(min(v[i],v[i+1]));
  }
  ans.pb(v[n-2]);
  for(ll i=0;i<n;i++)
  {
    val+=ans[i];
  }
  cout<<val;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int a,b,c,ans=0,ans2=0;
char ch;
int main(){
  while(cin>>a>>ch>>b>>ch>>c){
    if(a*a+b*b==c*c)ans++;
    if(a==b)ans2++;
  }
  cout<<ans<<endl<<ans2<<endl;
  return 0;
}

Measured memory_bytes: 1160
//g++ -std=gnu++14 a.cpp

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>
#include <stdio.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;
ll MODP = 998244353;

ll kai(ll x,ll y){
  if(y == 0)return 1;
  if(y == 1)return x;
  if(y&1){
    return (x*kai(x,y-1))%MOD;
  }else{
    ll t = kai(x,y/2);
    return (t*t)%MOD;
  }
}

ll comb(ll a,ll b,vector<ll> &p){
  if(a == 0)return 1;
  if(b == 0)return 1;
  ll ans = p[a+b];
  ans = (ans*kai(p[a],MOD-2))%MOD;
  ans = (ans*kai(p[b],MOD-2))%MOD;
  return ans;
}

ll mind(int x,vector<int> &v){
  int ok = v.size()-1,ng = -1;
  while(ok - ng > 1){
    int next = (ok+ng)/2;
    if(v[next] > x){
      ok = next;
    }else{
      ng = next;
    }
  }
  return ok;
}

ll maxd(int x,vector<int> &v){
  int ok = 0,ng = v.size();
  while(ng - ok > 1){
    int next = (ok+ng)/2;
    if(v[next] < x){
      ok = next;
    }else{
      ng = next;
    }
  }
  return ok;
}


int main(){
  int N;
  cin >> N;
  string s;
  cin >> s;
  int r = 0,ans= 0;
  rep(i,N){
    if(s.at(i) == 'R')r++;
  }
  rep(i,r){
    if(s.at(i) == 'W')ans++;
  }
  cout << ans << endl;

  return 0;
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> s;
    MSG(s.at(0) + to_string(s.size() - 2) + s.at(s.size() - 1))
}


Measured memory_bytes: 256
A,B=map(int,input().split())
DP=[float("INF")]*(A+1)
DP[0]=1
for i in range(B):
   DP[int(input())]=0
for i in range(A):
   if i==0:
      DP[i+1]=min(DP[i+1],DP[0])
   else:
      DP[i+1]=min(DP[i+1],DP[i]+DP[i-1])
print(DP[-1]%(10**9+7))

Measured memory_bytes: 460020
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,d,a;
cin>>n>>d>>a;
pair<int,int> arr[n];
for(int i=0;i<n;i++)
{
    cin>>arr[i].ff>>arr[i].ss;
}
sort(arr,arr+n);
int dp[n+1]={};
int inf=pow(10,15);
int ans=0;
for(int i=0;i<n;i++)
{if(i!=0)
    dp[i]+=dp[i-1];
    if(-1*dp[i]>=arr[i].ss)
    continue;
    int x=arr[i].ff;
    x=x+2*d;
    pair<int,int> r=make_pair(x,inf);
    int pos=upper_bound(arr,arr+n,r)-arr;
    int val=arr[i].ss+dp[i];
    int res=val/a;
   
    if(val%a!=0)
        res+=1; 
        ans+=res;
    dp[i]-=res*a;
    dp[pos]+=res*a;

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


Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();

		if (a <= c && c <= b) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 22868
from itertools import*
n,q=map(int,input().split())
s=input()
dp=[0]*n
for i in range(n-1):
    if s[i:i+2]=="AC":
        dp[i+1]=1
x=list(accumulate(dp))
for i in range(q):
    l,r=map(int,input().split())
    print(x[r-1]-x[l-1])

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

int main() {
  int n, k, x, y; cin >> n >> k >> x >> y;
  
  int ans = 0;
  for (int i=0; i<n; i++){
    if (i<k) ans += x;
    if (i>=k) ans += y;
  }
  
  cout <<ans <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <set>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<n+1;i++)
int main(){
    string N;
    cin>>N;
    ll ans=0;
    char n[1];
    reverse(N.begin(),N.end());
    N.append("0");
    int l = N.size();
    bool carry = false;
    rep(i,l){
        n[0] = N[i];
        if(carry){
            if ((N[i] == '0') || (N[i] == '1') ||(N[i] == '2') ||(N[i] == '3')){
                ans += atoi(n)+1;
                carry = false;
            }else if(N[i] =='4'){
                n[0] = N[i+1];
                if(atoi(n)<5){
                    ans += 5;
                    carry = false;
                }else{
                    ans += 5;
                    carry = true;
                }
            }else if(N[i] != '9'){
                ans += 9 -(atoi(n));
                carry =true;
            }else{
                carry = true;
            }
        }else{
            if ((N[i] == '0') || (N[i] == '1') ||(N[i] == '2') ||(N[i] == '3') ||(N[i] == '4')){
                ans += atoi(n);
                carry  = false;
            }else if(N[i] =='5'){
                n[0] = N[i+1];
                if(atoi(n)<5){
                    ans += 5;
                    carry = false;
                }else{
                    ans += 5;
                    carry = true;
                }
            }else{
                ans += 10-atoi(n);
                carry = true;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1412
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;


namespace atcorder2
{
    class Program
    {
        public static long Read()
        {

            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       
         public static long GCM(long x,long y)
        {
            if (x < y)  GCM(y, x);


            while (y > 0)
            {
                var z = y;
                y = x % y;
                x = z;
            }
            
            return x;
        }

        



        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);


            var s = ReadLine();
            var ans = new List<long>();
            for (int j = 'a'; j <= 'z'; j++)
            {
                var t = new bool[s.Length];
                var c = 0;
                for (int i = 0; i < s.Length; i++)
                {
                    if (s[i] == (char)j)
                    {
                        c++;
                        t[i] = true;
                     }
                }
                if (c != 0)
                {
                    bool f = true;
                    for (int i = 0; i < s.Length; i++)
                    {
                        if (!t[i]) f = false;
                    }
                    if (!f)
                    {
                        for (int i = 1; i <= s.Length; i++)
                        {
                            f = true;
                            for (int k = 1; k <= s.Length - i; k++)
                            {
                                if (t[k]) t[k - 1] = true;
                            }
                            for (int k = 0; k < s.Length - i; k++)
                            {
                                if (!t[k]) f = false;
                            }
                            if (f) { ans.Add(i); break; }
                        }

                    }
                    else ans.Add(0);
                }
            }
            WriteLine(ans.Min());


            Console.Out.Flush();
        }
    }
}




Measured memory_bytes: 13268
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
long long a,b,x;
cin>>a>>b>>x;
long long ans=0;
if(b-a>=x) {
    if(a%x==0) {ans=b/x-a/x+1;}
    else {ans=b/x-a/x;}
}
else {
    if(a/x==b/x&&a%x!=0&&b%x!=0) ans=0;
    else ans=1;
}

cout<<ans;
return 0;
}


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

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, d;
    cin >> n >> d;
    d = 2 * d + 1;
    cout << (n + d - 1) / d << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int a, b;

  while(scanf("%d %d", &a, &b) != EOF) {
    if((a + b) / 1000000 != 0) {
      printf("7");
    }
    else if((a + b) / 100000 != 0) {
      printf("6");
    }
    else if((a + b) / 10000 != 0) {
      printf("5");
    }
    else if((a + b) / 1000 != 0) {
      printf("4");
    }
    else if((a + b) / 100 != 0) {
      printf("3");
    }
    else if((a + b) / 10 != 0) {
      printf("2");
    }
    else {
      printf("1");
    }
    printf("\n");
  }

  return 0;
}

Measured memory_bytes: 568
INF = 100000000000

from itertools import product
N = int(input())
is_opens = []
all_open = [0 for i in range(10)]

for n in range(N):
  l = list(map(int, input().split()))
  for i in range(len(l)):
    all_open[i] = 1 if l[i] == 1 else all_open[i] 
  is_opens.append(l)
must_true = set([i for i in range(len(all_open)) if all_open[i] == 0])

values = []
for n in range(N):
  values.append(list(map(int, input().split())))

patterns = product([0,1], repeat=10)
ans = -INF
for pattern in patterns:
  trues = set([i for i in range(len(pattern)) if pattern[i] == 1])
  if not must_true.issubset(trues) or trues == set():
    continue 

  tmp = 0
  for n in range(N):
    count = sum([1 for i in range(10) if pattern[i] == 1 and pattern[i] == is_opens[n][i]])
    value = values[n][count]
    tmp += value
  ans = max(ans, tmp)

print(ans)
  


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(void){
    int a,b;

    cin >> a >> b;

    if(a>12){
        cout << b << endl;
    }else if(a>5){
        cout << b/2 << endl;
    }else{
        cout << 0 << endl;
    }
    return 0;
}

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

int main() {
    int H,W;
    int allBlack = 0;
    cin >> H >> W;
    vector<vector<int>> black;
    vector<vector<char>> mass(H, vector<char>(W, '.'));
    for(int i=0;i<H;i++){
        string s;
        cin >> s;
        for(int j=0;j<W;j++){
            if(s[j] == '#'){
                mass.at(i).at(j) = '#';
                black.push_back(vector<int>{i,j});
                allBlack++;
            }
        }
    }
    int numBlack = allBlack;
    int answer = 0;
    if(allBlack == H*W){
        cout << answer << endl;
        return 0;
    }
    while(true){
        vector<vector<int>> newBlack;
        int newNumBlack = 0;
        answer++;
        for(int i=0;i<numBlack;i++){
            int x,y;
            x = black.at(i).at(0);
            y = black.at(i).at(1);
            if(x-1 >= 0){
                if(mass.at(x-1).at(y) == '.'){
                    mass.at(x-1).at(y) = '#';
                    newBlack.push_back(vector<int>{x-1,y});
                    newNumBlack++;
                    allBlack++;
                }
            }
            if(x+1 < H){
                if(mass.at(x+1).at(y) == '.'){
                    mass.at(x+1).at(y) = '#';
                    newBlack.push_back(vector<int>{x+1,y});
                    newNumBlack++;
                    allBlack++;
                }
            }
            if(y-1 >= 0){
                if(mass.at(x).at(y-1) == '.'){
                    mass.at(x).at(y-1) = '#';
                    newBlack.push_back(vector<int>{x,y-1});
                    newNumBlack++;
                    allBlack++;
                }
            }
            if(y+1 < W){
                if(mass.at(x).at(y+1) == '.'){
                    mass.at(x).at(y+1) = '#';
                    newBlack.push_back(vector<int>{x,y+1});
                    newNumBlack++;
                    allBlack++;
                }
            }
        }
        if(allBlack == H*W){
            cout << answer << endl;
            break;
        }
        else{
            black = newBlack;
            numBlack = newNumBlack;
        }
    }

    return 0;
}

Measured memory_bytes: 57384
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long int 
signed main(){
    int n;
    cin >> n;
    vector<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];
    }
    int sum = 0;
    for(int i = 0; i < n; i++){
       sum += min(a[i],b[i]);
        b[i] -= min(a[i],b[i]);
        sum += min(b[i], a[i + 1]);
        if(a[i + 1] <= b[i])
        a[i + 1] = 0;
        else
        a[i + 1] -= b[i];
    }
    cout << sum << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include<cfenv>
using namespace std;
int main() {
    // insert code here...
    int N, K;
    int *h;
    int l;
    int cnt = 0;
    int i = 0;
    cin >> N;
    cin >> K;
    h = new int[N];
    while(i < N){
        cin >> h[i];
        if (h[i] >= K) cnt++;
        i++;
    }
    cout << cnt << endl;
    
    
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x 2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  int n;
  cin >> n;
  cout << (n+1)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
const double eps = 1e-8;
int main()
{
	double L;
	scanf("%lf", &L);

	double c = L / 3.0;
	double v = c * c * c;

	printf("%.12lf", v);

	
	

	return 0;
}

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

const unsigned long long bigp=(1ULL<<61)-1ULL;
const unsigned long long smallp=(1ULL<<31)-1ULL;
const unsigned long long smallpplus=(1ULL<<31);
const unsigned long long smallpminus=(1ULL<<30)-1ULL;

unsigned long long b=40787;

class hash_mod{
    public:
    unsigned long long val;
    unsigned long long val_u, val_d;
    unsigned long long another_u, another_d;
    unsigned long long m, m_u, m_d;

    void remainder(){
        val_u=(val>>61);
        val_d=val&bigp;
        if(val_u + val_d <bigp) val= val_u + val_d;
        else val= (val_u + val_d) -bigp;
    }

    void update(unsigned long long v){
        val=v;
        remainder();
    }

    void addition(unsigned long long another){
        val+=another;
        remainder();
    }

    void subtraction(unsigned long long another){
        val+=bigp;
        val-=another;
        remainder();
    }

    void multiple(unsigned long long another){
        val_u=(val>>31);
        val_d=val&smallp;
        another_u=(another>>31);
        another_d=another&smallp;
        m=val_u*another_d + val_d*another_u;
        m_u=(m>>30);
        m_d=m&smallpminus;
        val=0;
        val+=val_u*another_u*(2ULL);
        val+=m_u + m_d*smallpplus;
        val+=val_d*another_d;
        remainder();
    }
};

int main(){
    //input
    unsigned long long N;
    string S;
    cin >> N >> S;

    //calc
    unsigned long long i,j;
    hash_mod S_hash;
    char c='a';
    c--;
    hash_mod sub, b_pow[N/2];
    b_pow[0].update(1ULL);
    for(i=1; i<N/2; i++){
        b_pow[i].update(b);
        b_pow[i].multiple(b_pow[i-1].val);
    }

    for(i=N/2; i>=1; i--){
        set<pair<unsigned long long, unsigned long long> > st;
        set<pair<unsigned long long, unsigned long long> >::iterator it, itne;
        S_hash.update(0ULL);
        for(j=0; j<i; j++){
            S_hash.multiple(b);
            S_hash.addition((unsigned long long)(S[j]-c));
        }
        st.insert(make_pair(S_hash.val,0ULL));
        for(j=i; j<N; j++){
            sub.update((unsigned long long)(S[j-i]-c));
            sub.multiple(b_pow[i-1].val);
            S_hash.subtraction(sub.val);
            S_hash.multiple(b);
            S_hash.addition((unsigned long long)(S[j]-c));
            st.insert(make_pair(S_hash.val,j-(i-1)));
        }
        for(it=st.begin(); it!=st.end(); it++){
            itne=st.lower_bound(make_pair((*it).first+1ULL,0ULL));
            itne--;
            if((*it).second+i<=(*itne).second) break;
        }
        if(it!=st.end()) break;
    }

    //output
    cout << i << endl;
    system("pause");
    return 0;
}

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

int main(){
  string s;
  cin >> s;
  
  int zero = 0;
  int ichi = 0;
  
  for(int i = 0;i < s.size();i ++){
    if(s[i] == '0')zero ++;
    else ichi ++;
  }
  
  cout << min(zero,ichi) * 2 << endl;
}


Measured memory_bytes: 3760
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    n, m = getList()
    uf = UnionFind(n + 1)
    for i in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a, b)

    print(max(uf.size))
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Measured memory_bytes: 90340
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) long long((x).size())
#define OUT(x) cout << (x) << endl
typedef long long ll;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
typedef pair<ll, ll> P;
typedef map<string, ll> M;
typedef unordered_map<ll, ll> HM;
typedef set<ll> S;
typedef multiset<ll> MS;
typedef queue<ll> Q;

int main(){
    ll a,b; cin>>a>>b;
    OUT(max({a+b, a-b, a*b}));
}

Measured memory_bytes: 256
import sys



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


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    ng = 0
    ok = 10 ** 9 + 1
    A.sort(reverse=True)

    while ok - ng > 1:
        mid = (ok + ng) // 2
        ans =0
        for i in range(N):
            ans += A[i]//mid -1
            if A[i]%mid !=0:
                ans +=1
            if ans >K:
                break

        if ans <= K:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    main()


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

int main(void) {
  int n, k;
  cin >> n >> k;
  vector<int> xs(n);
  for (int &x : xs) {
    cin >> x;
  }

  int result = 0;
  for (const int &x : xs) {
    result += min(x, k - x) * 2;
  }

  cout << result << endl;
  return 0;
}

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

namespace SquareSearch
{
    class Program
    {
        static char GetCharOrDefault(string s, int index, char defaultChar)
        {
            if (s == null || index < 0 || s.Length <= index)
            {
                return defaultChar;
            }

            return s[index];
        }


        static bool SearchSquare(string line, int[] lengthOfColumns, int targetSquareLength)
        {
            var isFound = false;

            var count = 0;
            for (var i = 0; i < lengthOfColumns.Length; ++i) { 
                if (GetCharOrDefault(line, i, ' ')  == '*') {
                    lengthOfColumns[i] = 0;
                }
                else {
                    ++lengthOfColumns[i];
                }

                if (targetSquareLength <= lengthOfColumns[i])
                {
                    ++count;
                    if (targetSquareLength <= count)
                    {
                        isFound = true;
                    }
                }
                else
                {
                    count = 0;
                }
            }

            return isFound;
        }


        static int GetLargetSquareLength(int rank, IEnumerable<string> lines)
        {
            var columns = new int[rank];
            var targetSquareLength = 1;
            foreach (var s in lines)
            {
                if (SearchSquare(s, columns, targetSquareLength))
                {
                    ++targetSquareLength;
                }
            }
            return targetSquareLength - 1;
        }


        static IEnumerable<string> ReadLines(int count)
        {
            for (var i = 0; i < count; ++i)
            {
                yield return Console.ReadLine();
            }
        }


        static void Main(string[] args)
        {
            var answer = new List<int>();

            while (true) 
            {
                var input = Console.ReadLine();
                var rank = 0;
                {
                    if (int.TryParse(input, out rank) == false)
                    {
                        break;
                    }

                    if (rank == 0)
                    {
                        break;
                    }
                }

                var length = GetLargetSquareLength(rank, ReadLines(rank));
                answer.Add(length);
            }

            foreach (var n in answer) {
                Console.WriteLine(n);
            }
        }
    }
}

Measured memory_bytes: 7928
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N, C;
    cin >> N >> C;
    vector<int> vec(100005, 0), tmp(100005, 0);
    vector<vector<int>> data(N, vector<int> (3));
    int s,t,c;
    for (int i = 0; i < N; i++) {
        cin >> data[i][0] >> data[i][1] >> data[i][2];
    }
    for (int c = 1; c <= C; c++) {
        for (int i = 0; i < N; i++) {
            if(data[i][2] == c){
                tmp[data[i][0]]++;
                tmp[data[i][1]]--;
            }
        }
        for (int i = 0; i < 100005; i++) {
            if(tmp[i] == 1){
                vec[i-1]++;
            }
            else if(tmp[i] == -1){
                vec[i]--;
            }
        }
        for (int i = 0; i < 100005; i++) {
            tmp[i] = 0;
        }
    }

    int ans, tm;
    tm = 0; ans = 0;
    for (int i = 0; i < 100005; i++) {
        tm += vec[i];
        ans = max(ans, tm);
    }

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


}


Measured memory_bytes: 6528
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  string s;
  cin >> s;

  if (s.size() == 2) {
    cout << s << endl;
  } else {
    cout << s[2] << s[1] << s[0] << endl;
  }
}


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

using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr int NMAX = 500010;

ll fact[NMAX], invfact[NMAX];

ll modexp(ll b, ll e) {
	if (e == 0) return 1;
	else return (e & 1 ? b : 1) * modexp(b * b % MOD, e/2) % MOD;
}

ll binom(ll n, ll k) {
	return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}

ll FMOD(ll x) {
	return (x % MOD + MOD) % MOD;
}

int main() {
	int n, m; scanf("%d %d", &n, &m);
	fact[0] = 1;
	for (int i = 1; i < NMAX; ++i) fact[i] = (fact[i-1] * i) % MOD;
	invfact[NMAX - 1] = modexp(fact[NMAX - 1], MOD - 2);
	for (int i = NMAX - 2; i >= 0; --i) invfact[i] = (i + 1) * invfact[i+1] % MOD;
	ll ans = 0;
	for (int k = 0; k <= n; ++k) {
		ll innerWays = binom(m - k, n - k) * fact[n - k] % MOD;
		ll term = binom(n, k) * binom(m, k) % MOD * fact[k] % MOD * innerWays % MOD * innerWays % MOD;
//		printf("%d term %lld\n", k, (k % 2 == 0 ? 1 : -1) * term);
		ans = (ans +  FMOD((k % 2 == 0 ? 1 : -1) * term)) % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 11536
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<sstream>
using namespace std;

#define pi acos(-1.0)
#define ms(x,n) memset(x,n,sizeof(x));

typedef long long ll;//string::npos
typedef long long iint;

ll gcd(ll a,ll b) {
	return a%b==0?b:gcd(b,a%b);
}
ll lcm(ll x,ll y) {
	ll z=gcd(x,y);
	return x*y/z;
}

const int MAXX=2e5+5;
const int INF=1e7+5;
const int mod=998244353;

vector<int> vt;
map<int,int> m1;

int main() {
	ios::sync_with_stdio(false);
	long long n,a,b;
	while(cin>>n>>a>>b){
		if(n%(a+b)==0){
			cout<<n/(a+b)*a<<endl;
		}else{
			if(a+b>n){
				cout<<min(n,a)<<endl;
			}else{
//				long long sum=n/(a+b)*a;
//				sum=sum+
				cout<<n/(a+b)*a + min(n%(a+b),a)<<endl;
			}
			
		}
	}
	
	return 0;
}




//	getline(cin,a);
//	scanf("%[^\n]",a);getchar();
//	cin.getline(a,sizeof(a));

Measured memory_bytes: 256
(defun count-RGB (s c)
  (let ((counter 0))
    (loop :for i :across s
          :do (if (string= i c) (incf counter)))
    counter))

(defun RGB-Triplets (n s)
    (let ((ans 0))
        (incf ans (* (* (count-RGB s "R") (count-RGB s "G") (count-RGB s "B"))))
        (loop
            :for i :from 0 :to (- n 2)
            :do (loop
                    :for j :from i :to (- n 1)
                    :do (cond
                            ((/= (mod (- j i) 2) 0) ())
                            ((string= (char s i) (char s j)) ())
                            ((string= (char s i) (char s (/ (+ i j) 2))) ())
                            ((string= (char s j) (char s (/ (+ i j) 2))) ())
                            (t (decf ans)))))
        ans))

(princ (RGB-Triplets (read) (read-line)))

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

int main() {
  int r, c, a[110][110] = {0};
  cin >> r >> c;
  for (int i=0;i<r;i++)
    for (int j=0;j<c;j++) {
      cin >> a[i][j];
      a[i][c] += a[i][j];
      a[r][j] += a[i][j];
      a[r][c] += a[i][j];
    }

  for (int i=0;i<r+1;i++) {
    for (int j=0;j<c;j++)
      cout << a[i][j] << " ";
    cout << a[i][c];
    cout << endl;
  }
}



Measured memory_bytes: 3132
S = gets.chomp.to_i

if S/100 > 0 && S/100 < 13
  if S%100 > 0 && S%100 < 13
    puts "AMBIGUOUS"
  else
    puts "MMYY"
  end
else
  if S%100 > 0 && S%100 < 13
    puts "YYMM"
  else
    puts "NA"
  end
end

Measured memory_bytes: 1788
A, B = map(int, input().split())
if A % 3 == 0:
    s = 'Possible'
elif B % 3 == 0:
    s = 'Possible'
elif (A + B) % 3 == 0:
    s = 'Possible'
else:
    s = 'Impossible'
print(s)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    int count=-1;
    bool flag=true;
    
    for(int i=0;i<N;i++){
        cin >> A[i];
    }

    while(flag){    



        for(int i=0; i<N; i++){
             if(A[i] % 2 == 1){
                flag=false;
                break;
            }
            A[i] = A[i] / 2;

        }
        count++;
    }

    cout << count << endl;
}

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

int N;
ll a[405];

int main(){
	cin >> N;
	ll c[405] = {0};
	for (int i = 1; i <= N; ++i) cin >> a[i];
	for (int i = 1; i <= N; ++i) c[i] = c[i-1] + a[i];	//partial sum
	//min cost starting from ith slime to jth slime
	ll dp[N+1][N+1];
	memset(dp,1000000005,sizeof(dp));
	for (int i = 1; i <= N; ++i) dp[i][i] = 0;
	//exhaust left, right
	for (int L = N; L > 0; --L){
		for (int R = L + 1; R <= N; ++R){
			//exhaust mid-point (sum of previous cost)
			for (int M = L; M < R; ++M){
				dp[L][R] = min(dp[L][R], dp[L][M] + dp[M+1][R]);	
			}
			//cost for this combination (sum from L to R)
			dp[L][R] += c[R] - c[L-1];
		}
	}
	cout << dp[1][N] << '\n';
	return 0;
}

Measured memory_bytes: 1536
//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printdbe) FUNC(printdwe) FUNC(printdu) FUNC(printe) FUNC(printe0);
#endif
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

int twofives[60][60];
int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    // vector<ll> as;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        ll num = 0;
        int pos = s.find('.');
        if(pos >= 0){
            int idx = 0;
            while(idx < pos){
                num = num * 10 + s[idx] - '0';
                idx++;
            }
            idx++;
            for(int i = 0; i < 9; i++){
                num = num * 10 + (idx < (int)s.size() ? s[idx] - '0' : 0);
                idx++;
            }
        }else{
            int idx = 0;
            while(idx < (int)s.size()){
                num = num * 10 + s[idx] - '0';
                idx++;
            }
            for(int i = 0; i < 9; i++){
                num = num * 10;
            }
        }
        // as.push_back(num);
        int two = 0, five = 0;
        while(num % 2 == 0){ two++; num /= 2; }
        while(num % 5 == 0){ five++; num /= 5; }
        twofives[two][five]++;
    }
    // printde(as);
    printde(twofives);
    ll ans = 0;
    for(int i1 = 0; i1 < 60; i1++){ for(int j1 = 0; j1 < 60; j1++){
        for(int i2 = 0; i2 < 60; i2++){ for(int j2 = 0; j2 < 60; j2++){
            if(i1 == i2 && j1 == j2){ continue; }
            if(i1 + i2 < 18 || j1 + j2 < 18){ continue; }
            // if(i1 + i2 < 9 || j1 + j2 < 9){ continue; }
            ans += 1ll * twofives[i1][j1] * twofives[i2][j2];
            if(twofives[i1][j1] * twofives[i2][j2]){
                printde(i1, j1, i2, j2, ans);
            }
        } }
    } }
    ans /= 2;
    for(int i1 = 0; i1 < 60; i1++){ for(int j1 = 0; j1 < 60; j1++){
        if(i1 >= 9 && j1 >= 9){
            ans += 1ll * twofives[i1][j1] * (twofives[i1][j1] - 1) / 2;
        //     ans -= 1ll * twofives[i1][j1] * twofives[i1][j1];
        }
    } }
    cout << ans << '\n';
}


Measured memory_bytes: 3228
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
template<typename Monoid>
struct SegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	int sz;
	vector<Monoid> seg;
	const F f;
	const Monoid e;

	SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
	}

	SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
		for(int i=0; i<n; i++) seg[i+sz]=v[i];
		for(int i=sz-1; i>=1; i--){
			seg[i]=f(seg[2*i], seg[2*i+1]);
		}
	}

	void update(int k, const Monoid &x){
		k+=sz;
		seg[k]=x;
		while(k>1){
			k>>=1;
			seg[k]=f(seg[2*k], seg[2*k+1]);
		}
	}

	Monoid query(int a, int b){
		a+=sz, b+=sz;
		Monoid ret=e;
		for(;a<b; a>>=1, b>>=1){
			if(b&1) ret=f(ret, seg[--b]);
			if(a&1) ret=f(ret, seg[a++]);
		}
		return ret;
	}

	template<typename C>
	int binarysearch(int st, C &check, Monoid &s, int k, int l, int r){//[st,ret):false, [st, ret+1):true (check(e):false)
		if(k>=sz){
			s=f(s, seg[k]);
			if(check(s)) return k-sz;
			else return -1;
		}
		int m=(l+r)>>1;
		if(m<=st) return binarysearch(st, check, s, 2*k+1, m, r);
		if(st<=l && !check(f(s, seg[k]))){
			s=f(s, seg[k]);
			return -1;
		}
		int vl=binarysearch(st, check, s, 2*k, l, m);
		if(vl!=-1) return vl;
		return binarysearch(st, check, s, 2*k+1, m, r);
	}
	
	template<typename C>
	int binarysearch(int st, C &check){
		Monoid s=e;
		return binarysearch(st, check, s, 1, 0, sz);
	}

	Monoid operator[](const int &k) const{
		return seg[k+sz];
	}
};
int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    vector<int> a(n);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    SegmentTree<int> seg(n, [](int x, int y){ return max(x, y);}, -1, a);
    while(q--){
        int t;
        scanf("%d", &t);
        if(t==1){
            int x, v;
            scanf("%d %d", &x, &v);
            x--;
            seg.update(x, v);
        }else if(t==2){
            int l, r;
            scanf("%d %d", &l, &r);
            l--;
            printf("%d\n", seg.query(l, r));
        }else{
            int x, v;
            scanf("%d %d", &x, &v);
            x--;
            auto check=[&](int a){ return a>=v;};
            int r=seg.binarysearch(x, check);
            if(r!=-1) printf("%d\n", r+1);
            else printf("%d\n", n+1);
        }
    }
    return 0;
}


Measured memory_bytes: 7020
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct edge {
  int to;
  int cost;
  edge(int t = 0, int c = 0)
    : to(t), cost(c) {};
};

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

  vector<vector<edge>> tree(n);

  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    tree[u].push_back(edge(v, w));
    tree[v].push_back(edge(u, w));
  }

  vector<int> ans(n, -1);
  queue<int> q({ans[0] = 0});

  while (!q.empty()) {
    auto v = q.front(); q.pop();
    for (int i = 0; i < int(tree[v].size()); i++) {
      auto to = tree[v][i].to;
      auto cost = tree[v][i].cost;
      if (ans[to] >= 0) continue;
      ans[to] = (ans[v] + cost) % 2;
      q.push(to);
    }
  }

  for (auto&& a : ans) {
    cout << a << endl;
  }
}


Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 100002;

class Seg_Tree{
public:
	vector<int> dat;
	int n;
	void initsize(int n0){
		int k=1;
		while(1){
			if(n0<=k){
				n=k;
				dat.resize(2*n-1);
				for(int i=0;i<2*n-1;i++)dat[i]=INT_MAX;
				break;
			}
			k*=2;
		}
	}

	//i banme wo x nisuru
	void update(int i,int x){
		i += n-1;
		dat[i] = x;
		while(i>0){
			i = (i-1) / 2;
			dat[i] = min(dat[i*2+1],dat[i*2+2]);
		}
	}

	//[a,b)
	int query0(int a,int b,int k,int l,int r){
		if(r<=a || b<=l)return INT_MAX;
		if(a<=l && r<=b)return dat[k];
		else{
			int vl = query0(a,b,k*2+1,l,(l+r)/2);
			int vr = query0(a,b,k*2+2,(l+r)/2,r);
			return min(vl,vr);
		}
	}

	//min [a,b)
	int query(int a,int b){
		return query0(a,b,0,0,n);
	}
};



int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	Seg_Tree s;
	s.initsize(n);
	FOR(i,0,q){
		int c,x,y;
		cin>>c>>x>>y;
		if(c==0)s.update(x,y);
		else{
			cout<<s.query(x,y+1)<<endl;
		}
	}
	return 0;
}



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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max()/2;
const int MOD = 1e9+7;

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

    int n;
    while(cin>>n,n){
        vector<string> stmp(n);
        for(int i=0;i<n;i++) cin>>stmp[i];
        vector<string> s;
        for(int i=0;i<n;i++){
            bool f=false;
            for(int j=0;j<n;j++){
                if(i==j) continue;
                int len1=stmp[i].length(),len2=stmp[j].length();
                if(len1>len2) continue;
                for(int st=0;st<len2-len1;st++){
                    if(stmp[i] == stmp[j].substr(st,len1)) f=true;
                }
            }
            if(!f) s.push_back(stmp[i]);
        }
        n=s.size();
        vector<vector<int>> c(n,vector<int>(n,INF));
        for(int i=0;i<n;i++){
            c[i][i]=0;
            for(int j=0;j<n;j++){
                if(i==j) continue;
                c[i][j]=s[j].length();
                int len1=s[i].length(),len2=s[j].length();
                if(len1>len2){
                    for(int st=len1-len2;st<len1;st++){
                        int nl=len1-st;
                        string sub1=s[i].substr(st,nl),sub2=s[j].substr(0,nl);
                        if(sub1==sub2) c[i][j]=min(c[i][j],len2-nl);
                    }
                }
                else{
                    for(int st=0;st<len1;st++){
                        int nl=len1-st;
                        string sub1=s[i].substr(st,nl),sub2=s[j].substr(0,nl);
                        if(sub1==sub2) c[i][j]=min(c[i][j],len2-nl);
                    }
                }
                //cout<<i<<" "<<j<<" "<<c[i][j]<<endl;
            }
        }
        vector<vector<int>> dp((1<<n),vector<int>(n,INF));
        for(int i=0;i<n;i++){
            dp[1<<i][i] = s[i].length();
        }
        for(int i=1;i<(1<<n);i++){
            int num=i;
            for(int j=0;j<n;j++){
                for(int k=0;k<n;k++){
                    if(((num>>j)&1)==0 || ((num>>k)&1)==1) continue;
                    dp[i | (1<<k)][k]=min(dp[i | (1<<k)][k],dp[i][j] + c[j][k]);
                }
            }
        }
        int res=INF;
        for(int i=0;i<n;i++){
            res=min(res,dp[(1<<n)-1][i]);
        }
        cout<<res<<endl;
    }
}


Measured memory_bytes: 4296