akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue> 
#include <cassert>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

#define INF 2000000000
#define MOD 1000000007

using namespace std;

int main() {
	long long a, b, c, d;
	long long n;
	cin >> n >> a >> b >> c >> d;
	if (a < b)
		swap(a, b);
	if (a - b > (n - 1LL) * d) {
		cout << "NO" << endl;
		return 0;
	}
	if (n == 2 && a != b) {
		cout << "NO" << endl;
		return 0;
	}
	for (int i = 1; i < n; i++) {
		long long l = a - d * i;
		long long r = a - c * i;
		long long L = l + (n - i - 1) * c;
		long long R = r + (n - i - 1) * d;
		if (b >= L && b <= R) {
			cout << "YES" << endl;
			return 0;
		}
		L = l - (n - i - 1) * d;
		R = r - (n - i - 1) * c;
		if (b >= L && b <= R) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  int M = 90;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A;
    int j = 0;
    
    while (true) {
      if (A % 2 == 1) {
        break;
      }
      else {
        A /= 2;
        j++;
      }      
    }
    
    if (M > j) {
      M -= (M - j);
    }
    
  }
  cout << M << endl;
  
}

Measured memory_bytes: 3456
#include<stdio.h>
int main(void)
{
	int i,j,n,n1;
	int a,b,c,d;
	int cnt[100];
	int sum[100];
	
	scanf("%d",&n);
	n1=n*(n-1)/2;
	for (i=0; i<n; i++) {
		sum[i]=0;
		cnt[i]=1;
	}
	for(i=0;i<n1;i++){
		scanf("%d %d %d %d",&a,&b,&c,&d);
		if(c>d){
			sum[a-1]+=3;
		}
		else if(c<d){
			sum[b-1]+=3;
		}
		else{
			sum[a-1]+=1;
			sum[b-1]+=1;
		}
	}
	for (i=0; i<n;i++) {    
		for (j=0;j<n;j++){
			if(sum[i]<sum[j]){
				cnt[i]++;
				
			}
		}
		printf("%d\n",cnt[i]);
	}
	return 0;
}

Measured memory_bytes: 1032
N = int(input())
ABC = [[int(_) for _ in input().split()] for _ in range(N)]
dp = [0, 0, 0]
for a, b, c in ABC:
    dp = [a + max(dp[1:]), b + max([dp[0], dp[2]]), c + max(dp[:2])]
print(max(dp))


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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

// index が条件を満たすかどうか
bool isOK(vector<ll> &A, ll index, ll key) {
    if (A[index] > key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
ll bin_search(vector<ll> &A, ll key) {
    ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll right = (ll)A.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        ll mid = left + (right - left) / 2;

        if (isOK(A, mid, key)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

int main(){

    int N,M,K;
    cin >> N >> M >> K;
    vector<ll> A,B;
 
    A.push_back(0);
    B.push_back(0);
 
    rep(i,N) {
        ll a;
        cin >> a;
        A.push_back(A[i]+a);
    }
    rep(i,M){
        ll b;
        cin >> b;
        B.push_back(B[i]+b);
    }
    ll amax = bin_search(A,K);
    amax--;
    ll ans = 0;
    for (ll i = amax; i>=0; i--) {
        ll res = K - A[i];
        ll bmax = bin_search(B,res);
        bmax--;
        //cout << res << " " << bmax << " " << i << endl;
        ans = max(ans,bmax+i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 7944
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define MAX 100000+1

using namespace std;

int main()
{
   int n,m,l,r,L=MAX,R=0;
   cin>>n>>m;
   int a[n+2]={0};
   for(int p=1; p<=m; p++)
   {
      cin>>l>>r;
      L=min(l,L);R=max(r,R);
      //for(int i=l; i<=r; i++)
          //a[i]+=1;
      a[l] += 1; a[r+1]-=1;
   }
  for(int i=1; i<=n; i++)
       a[i]+=a[i-1];
   int cnt=0;
   for(int i=L; i<=R; i++)
   {
      //a[i]+=a[i-1];
      if(a[i]==m)cnt++;
      
   }
   cout<<cnt;
   return 0;
}

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

int main() {
  long long n;
  cin>>n;
  vector<long long> a(n);
  for(int i=0;i<n;i++){
    cin>>a.at(i);
  }
  long long sum=0;
  for(int i=0;i<n;i++){
    sum=(sum+a.at(i))%1000000007;
  }
  long long ans=0;
  ans=(sum*sum)%1000000007;
  for(int i=0;i<n;i++){
    ans=(ans-(a.at(i)*a.at(i))%1000000007)%1000000007;
  }
  if(ans<0){
    ans=1000000007+ans;
  }
  ans=((ans*1000000008)/2)%1000000007;
  cout<<ans;
}

Measured memory_bytes: 4824
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] line1 = line.split(" ");
        int n = Integer.parseInt(line1[0]);
        int k = Integer.parseInt(line1[1]);
        String line2 = sc.nextLine();
        String[] line3 = line2.split(" ");
        int[] ary = new int[n];
        for(int i = 0; i < n; i++)  ary[i] = Integer.parseInt(line3[i]);
        int[] dp = new int[n];
        double d1 = Double.POSITIVE_INFINITY;
        for(int i = 0; i < n; i++)  dp[i] = (int)d1;
        dp[0] = 0;
        if(ary[0] > ary[1]) dp[1] = ary[0] - ary[1];
        else    dp[1] = ary[1] - ary[0];
        for(int i = 2; i < n; i++){
            for(int j = 0; j <= k; j++){
                int a = i - k;
                if(i - k < 0)   a = 0;
                if(i == j)  break;
                if(dp[i] >= dp[a + j] + absoluteValue(ary[a + j], ary[i])){
                    dp[i] = dp[a + j] + absoluteValue(ary[a + j], ary[i]);
                }
            }
        }
        System.out.println(dp[n - 1]);
    }
    static int absoluteValue(int a, int b){
        if(a > b)   return a - b;
        else    return b - a;
    }
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    ll X, N;
    cin >> X >> N;
    map<ll, ll> p;
    ll a;
    rep(0, i, N)
    {
        cin >> a;
        p[a]++;
    }
    ll ans, m = 10000;
    rep(-200, i, 200)
    {
        if (p[i] != 0)
        {
            continue;
        }
        ll tmp = m;
        m = min(m, abs(X - i));
        if (m != tmp)
        {
            ans = i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3664
import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
            # 即座に探索を終了する. これによりループの回数は最大でもM+1回となる.
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)

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

#define ll long long 

int main() {
    ios::sync_with_stdio(0); 

    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (auto& x : p) cin >> x;

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

    ll ans = 0;
    for (int i = 0; i < k; i++) {
        ans += p[i];
    }

    cout << ans << endl;


    return 0; 
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
const ll MOD = 1e9+7;

#define MAX_N 300100

ll fact[MAX_N+100];
ll frev[MAX_N+100];

ll rev(ll a, ll p){
    if(p == 0) return 1;
    ll tmp = rev(a, p/2);
    tmp = tmp * tmp % MOD;
    if(p % 2 == 1) tmp = tmp * a % MOD;
    return tmp;
}


void calc_fact(){
    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }
}


ll comb(int n, int k){
    if(n < 0 || k < 0 || n < k) return 0;
    if(n == 0 || k == 0) return 1;
    return fact[n] * frev[k] % MOD * frev[n-k] % MOD;
}


int main(){
    ll H, W, A, B;
    cin >> H >> W >> A >> B;
    int px = B;
    int py = H-A-1;
    ll ans = 0;

    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }

    int x = px;
    int y = py;
    while(1){
        if(x >= W || y < 0) break;
        ll s = comb(x+y, x) % MOD;        
        ll t = comb(W+H-x-y-2, W-x-1) % MOD;
        ans += s*t;
        ans %= MOD;
        x++;
        y--;
    }

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


Measured memory_bytes: 4992
n,k = gets.chomp.split(' ').map(&:to_i)

a = gets.chomp.split(' ').map(&:to_i)

set = {}
a.each do |b|
  set[b.to_s] ||= 0
  set[b.to_s] +=1
end

if set.length <= k
  puts 0
  exit
end

set2 = set.sort{|(k1, v1), (k2, v2)|v1<=>v2}

count = 0
(set.length-k).times do |i|
  count+=set2[i][1]
end

puts count

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

int main()
{
    int n,cnt,ans;

    cin >> n; 
    vector<int> h(n);
    rep(i, n) {
        cin >> h[i];
    }

    ans =0;
    cnt = 0;
    rep(i,n-1) {
        if (h[i] < h[i + 1]) {
            ans = max(ans, cnt);
            cnt = 0;
        }
        else {
            ++cnt;
        }
    }
    ans = max(ans, cnt);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3760
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, int M, int[][] pairs)
        {
            int L = 0;
            int R = int.MaxValue;
            foreach (int[] pair in pairs)
            {
                L = Math.Max(pair[0], L);
                R = Math.Min(pair[1], R);
            }
            return Math.Max(R - L + 1, 0);
        }

        static void Main(string[] args)
        {
            int[] V = ReadInts();
            int N = V[0], M = V[1];
            var pairs = new int[M][];
            for (int i = 0; i < M; ++i) { pairs[i] = ReadInts(); }
            Console.WriteLine(Solve(N, M, pairs));
        }
    }
}


Measured memory_bytes: 23624
MAX_SIZE = 10**5 + 1
is_prime = [True] * MAX_SIZE
is_prime[0] = False
is_prime[1] = False
for i in range(MAX_SIZE):
    if is_prime[i]:
        for j in range(2*i, MAX_SIZE, i):
            is_prime[j] = False
dp = [0] * MAX_SIZE
for i in range(1, MAX_SIZE):
    dp[i] = dp[i-1] + int(is_prime[i] & is_prime[(i+1) / 2])
q = input()
for i in range(q):
    l, r = map(int, raw_input().split())
    print dp[r] - dp[l-1]

Measured memory_bytes: 9452
from math import acos, sqrt, degrees
a,b,vol = map(int, input().split())

DEBUG = False
cap = a**2*b
area_tilt = vol/a

if DEBUG:
    print('vol = %d'%vol)
    print('cap = %f'%cap)
    
if vol <= cap/2:
    base = 2*area_tilt/b
    hypo = sqrt(base*base+b*b)
    deg = degrees(acos(b/hypo))
    deg_tilt = 90.0-deg
else: 
    short = b-(2*area_tilt/a - b)
    hypo = sqrt(short*short+a*a)
    deg = degrees(acos(short/hypo))
    deg_tilt = 90.0-deg

if DEBUG:
    print('short = %f'%short)
    print('hypo  = %f'%hypo)
    
print(deg_tilt)

Measured memory_bytes: 3064
import math
def gcd(m, n):
    x = max(m,n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z
def lcm(m, n):
    return int(m*n/gcd(m,n))
a, b = map(int, input().split())
print(lcm(a,b))

Measured memory_bytes: 38256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		String o = fs.next();
		String e = fs.next();
		
		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < o.length() + e.length(); i++) {
			if(i % 2 == 0) {
				int index = i/2;
				sb.append(o.charAt(index));
			}else {
				int index = i/2;
				sb.append(e.charAt(index));
			}
		}
		
		System.out.println(sb.toString());
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


Measured memory_bytes: 23124
import std.stdio;
import std.algorithm;
import std.string;
import std.conv;

void main(){

    int sum = 0;
    int num = 0;
    int count = 0;
    while(true){
	auto s = readln();
	if(stdin.eof()) break;
	string[] n1 = split(chomp(s),',');
	int[2] n;
	n = [to!int(n1[0]),to!int(n1[1])];
	sum += n[0] * n[1];
	num += n[1];
	count++;
    }
    real ans = to!real(num)/to!real(count);
    int res;
    ans *= 10;
    if(ans%10 >= 5) res = to!int(ans)/10 + 1;
    else res = to!int(ans);
    writeln(sum);
    writeln(res);
}

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

#define ll long long
#define db double
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ino freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);

#define fr(i,n) for(i=0;i<n;i++)
#define frs(i,a,n) for(i=a;i<n;i++)
#define frv(i,n) for(i=n-1;i>=0;i--)

#define ne cout<<"\n";
#define cas(i) cout<<"Case #"<<i<<": "

#define vi vector <int>
#define vpi vector <pair <int,int> >
#define vpin(v,a,b) v.push_back(make_pair(a,b))
#define vsort(v) sort(v.begin(),v.end());
#define all(v) ((v).begin()),((v).end())
#define sz(v) ((int)((v).size()))

#define todegree(rad) rad*(180.0/pi)
#define isnttriangle(a,b,c) (a+b<c||a+c<b||b+c<a)
#define pi acos(-1)
#define siz 1000


int main()
{
    ll H,W,ans,r,c;
    cin>>H>>W;
    if(H==1||W==1) ans=1;
    else if(H%2==0)
    {
        ans=(H/2)*W;
    }
    else if(W%2==0)
        ans=(W/2)*H;
    else
    {
        ans=(H/2)*W;
        ans+=(W/2)+1;
    }
    cout<<ans<<'\n';
    return 0;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
using Graph = vector<vector<int>>;

int main() {
  int H,W; cin >> H >> W;
  vector<string> S(H);
  rep(i,H) cin >> S[i];
  
  vector<vector<int>> L(H,vector<int>(W,1)), R(H,vector<int>(W,1)), U(H,vector<int>(W,1)), D(H,vector<int>(W,1));
  rep(i,H) {
    rep(j,W) {
      if (S[i][j]== '#') L[i][j] = 0;
      else if (j > 0) L[i][j] = L[i][j-1] + 1; 
    }
  }
  rep(i,H) {
    rep(j,W) {
      if (S[i][W-1-j]== '#') R[i][W-1-j] = 0;
      else if (j > 0) R[i][W-1-j] = R[i][W-j] + 1; 
    }
  }
  rep(j,W) {
    rep(i,H) {
      if (S[i][j]== '#') U[i][j] = 0;
      else if (i > 0) U[i][j] = U[i-1][j] + 1; 
    }
  }
  rep(j,W) {
    rep(i,H) {
      if (S[H-1-i][j]== '#') D[H-1-i][j] = 0;
      else if (i > 0) D[H-1-i][j] = D[H-i][j] + 1; 
    }
  }
  
  int count;
  int ans = 0;
  rep(i,H) {
    rep(j,W) {
      count = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3;
      ans = max(ans,count); 
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 67200
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
q = int(input())
query = [list(map(int, input().split())) for i in range(q)]


graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    
query = query[::-1]

dp = [-1] * (n * (10 + 1))
# dp = [[-1] * (10 + 1) for i in range(n)]
# [v][d] -> [v * 11 + d]
first = [0] * n

def solve(v, d, c):
    if d < 0 or dp[v * 11 + d] != -1:
        return
      
    dp[v * 11 + d] = c
    if first[v] == 0:
        first[v] = c

    solve(v, d - 1, c)
    for u in graph[v]:
        solve(u, d - 1, c)
    return
  

for v, d, c in query:
    v -= 1
    solve(v, d, c)

for i in range(n):
    print(first[i])

Measured memory_bytes: 122332
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

internal static class CR
{
    public static string GetText() { return Console.ReadLine(); }
    public static List<string> GetTexts() { return Console.ReadLine().Split(' ').ToList(); }
    public static long GetLong() { return long.Parse(Console.ReadLine()); }
    public static List<long> GetLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }
}

namespace AtCoder.C
{
    public class Program
    {
        public static long N { get; private set; }
        public static long M { get; private set; }

        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var inputs = CR.GetLongs();
            N = inputs[0];
            M = inputs[1];

            var sc = new List<SC>();
            for (int i = 0; i < M; i++)
            {
                inputs = CR.GetLongs();
                sc.Add(new SC
                {
                    S = inputs[0],
                    C = inputs[1],
                });
            }

            // 最大桁数が0ならNG
            if (N != 1 // 1桁のときは最大桁が0でもよい
                && sc.Any(x => x.S == 1 && x.C == 0)) return "-1";

            // 制約が破綻しているならNG
            foreach (var item in sc)
            {
                if (sc.Any(x => x.S == item.S && x.C != item.C)) return "-1";
            }

            // 1つも制約がなかった場合
            if (M == 0)
            {
                if (N == 1) return 0;
                if (N == 2) return 10;
                if (N == 3) return 100;
            }

            var result = "";
            for (int i = 1; i <= N; i++)
            {
                var v = sc.FirstOrDefault(x => x.S == i);
                if (v != null)
                {
                    result += v.C;
                }
                else
                {
                    result += i == 1 ? 1 : 0;
                }
            }
            return result;
        }
    }

    internal class SC
    {
        public long S { get; internal set; }
        public long C { get; internal set; }
    }
}


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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

const int nmax=100010;
int par[nmax],ranks[nmax],weight[nmax];

void init(int n){rep(i,n) par[i]=i,ranks[i]=0,weight[i]=0;}
int find(int x,int &w){
	if(par[x]==x)
		return x;
	else{
		w+=weight[x];
		return find(par[x],w);
	}
}

void unite(int a,int b,int c){
	int wa=0,wb=0;
	int pa=find(a,wa);
	int pb=find(b,wb);
	if(ranks[pa]<ranks[pb]){
		par[pa]=pb;
		weight[pa]=wb-wa+c;
	}else{
		par[pb]=pa;
		weight[pb]=wa-wb-c;
		if(ranks[pa]==ranks[pb]) ranks[pa]++;
	}
}

bool same(int a,int b,int& ans){
	int wa=0,wb=0;
	int pa=find(a,wa);
	int pb=find(b,wb);
	ans=wa-wb;
	return pa==pb;
}

int main(void){
	int n,m;
	while(cin >> n >> m,n){
		init(n);
		rep(i,m){
			char cmd;
			cin >> cmd;
			if(cmd=='!'){
				int a,b,c;
				cin >> a >> b >> c;
				unite(a-1,b-1,c);
			}else{
				int a,b,ans;
				cin >> a >> b;
				if(same(a-1,b-1,ans))
					cout << ans << endl;
				else
					cout << "UNKNOWN" << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 2336
// -*- coding: utf-8 -*-
// @Date    : 2019-11-09 19:18:00

#include <bits/stdc++.h>
#define greeting cerr << "What's your problem?\n"

using namespace std;
typedef long long ll;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& v)
{
	for(auto i : v)
		os << i << " ";
	return os;
}

template<typename T>
ostream& operator << (ostream& os, const set<T>& v)
{
	for(auto i : v)
		os << i << " ";
	return os;
}

#define locala
int main()
{
#ifdef local
	freopen("data.in", "r", stdin);
	freopen("ans.out", "w", stdout);
#endif	
	int n;
	scanf("%d", &n);
	printf("%d\n", n/2 - (1^(n&1)));
	return 0;
}

Measured memory_bytes: 256
using System;

public class Class1
{
		
		
	public static void Main()
	{   	
		int n = int.Parse(Console.ReadLine());
		int[,] cards = new int[4, 13];
		for (int i = 0; i < 4; i++) {   			
			for (int j = 0; j < 13; j++) {
				cards[i, j] = 0;
			}		
		}
			
		for (int i = 0; i < n; i++) {			
			string dataSet = Console.ReadLine();
			string[] data = dataSet.Split();
			int num = int.Parse(data[1])-1;
			switch (data[0]) {
				case "S":
					cards[0, num] = 1;
					break;
				case "H":
					cards[1, num] = 1;
					break;
				case "C":
					cards[2, num] = 1;
					break;
				case "D":
					cards[3, num] = 1;
					break;
			}
		}
		for (int i = 0; i < 4; i++) {			
			for (int j = 0; j < 13; j++) {     
				if (cards[i, j] == 0) {
					switch (i) {
						case 0:
							Console.WriteLine("S {0}", j+1);
							break;
						case 1:
							Console.WriteLine("H {0}" , j+1);			 				                  
							break;
						case 2:
							Console.WriteLine("C {0}" ,j+1);	
							break;
						case 3:
							Console.WriteLine("D {0}", j+1);	
							break;
					}
				}
			}
			
		}
	}
}
				
		
		
	

Measured memory_bytes: 9136
#include <iostream>

using namespace std;

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

	double result = 0;
	for (int i = 0; i < N; ++i)
	{
		double x;
		string v;
		cin >> x >> v;
		if (v == "JPY")
			result += x;
		else
			result += x * 380000.0;
	}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define foi(i,n) for(i = 0; i < n; i+=1)
#define fod(i,n) for(i=n-1; i >=0; i-=1)
#define MAX std::numeric_limits<lld>::max()
#define MIN std::numeric_limits<lld>::min()
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int main (){
    FastIO
    string s;
    cin >> s;
    lld n, i;
    n = s.length();
    lld f = 0;
    for(i = 1; i < n; i+=1){
    	if (s[i] != s[i-1]){
    		f = 1;
    		break;
    	}
    }
    if (f == 1)
    	cout << "Yes\n";
    else
    	cout <<  "No\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

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

int main(){
    ll N;
    cin>>N;
    rep(i,N,10000){
        bool ans = true;
        ll n = i;
        ll now = n % 10;
        n/=10;
        while(n>=1){
            if(n % 10 != now)ans = false; 
            n/=10;
        }
        if(ans){
            cout<< i;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		String str = reader.next();
		int ans1 = 0;
		int ans2 = 0;
		for (int i = 0; i < str.length(); i++) {
			char ch = str.charAt(i);
			if (Character.getNumericValue(ch) != i%2) {
				ans1++;
			}
			if (Character.getNumericValue(ch) != (i+1)%2) {
				ans2++;
			}
		}


		System.out.println(Math.min(ans1, ans2));
		reader.close();

	}

}





Measured memory_bytes: 26992
function parseInt(x) parse(Int, x) end
parseMap(x::Array{SubString{String}, 1}) = map(parseInt, x)

function isPrime(x)
	if x <= 1
		return(0)
	elseif x == 2
		return(1)
	elseif x%2 == 0
		return(0)
	else
		i = 3
		flg = 0
		while i <= floor(sqrt(x))
			if x%i == 0
				return(0)
				flg = 1
				break
			else
				i += 2
			end
		end
		if flg == 0
			return(1)
		end
	end
end

function isBPrime(x)
  if isPrime(x) == 1 && isPrime(div(x+1,2)) == 1
    return(1)
  else
    return(0)
  end
end

function main()
  x = Array{Int}(100000)
  x[1] = 0
  for i in 2:100000
  	x[i] = x[i-1]+isBPrime(i)
  end
  q = parseInt(readline())
  for i in 1:q
    l, r = parseMap(split(readline()))
    if l == 1
    	println(x[r])
    else
	    println(x[r]-x[l-1])
	end
  end
end

main()

Measured memory_bytes: 153388
import math


def main():
    N, K = map(int, input().split())
    print((max(0, N - K + 1) + sum(
        max(0, N - (math.ceil(K * (1 / 2) ** i)) + 1) * (1 / 2) ** i
        - max(0, N - (math.ceil(K * (1 / 2) ** (i - 1))) + 1) * (1 / 2) ** i
        for i in range(1, K))) / N)
    return


main()


Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
using namespace std;


int main()
{
	int A, B, C;
	bool flag=false;

	cin >> A >> B >> C;

	
	if(A==B && B==C){
		flag = false;
	}else if(A==B || B==C || C==A){
		flag = true;
	}else{
		flag = false;
	}

	cout << (flag ? "Yes" : "No");

	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] a = new long[n];
        for(int i=0; i<n; i++) a[i] = sc.nextLong();

        int m = 50;
        int[] num = new int[m];
        long[] pow2 = new long[m];
        pow2[0] = 1;
        for(int i=1; i<m; i++){
            pow2[i] = pow2[i-1]*2;
        }

        for(int i=0; i<n; i++){
            long atmp = a[i];
            for(int j=0; j<m; j++){
                if(atmp >= pow2[m-j-1]){
                    num[m-j-1]++;
                    atmp -= pow2[m-j-1];
                }
            }
        }

        // for(int i=0; i<m; i++){
        //     num[i] = Math.max(num[i], n-num[i]);
        // }

        long f = 0;
        for(int i=m-1; i>=0; i--){
            if(num[i] <= n/2){
                if(f + pow2[i] <= k){
                    f += pow2[i];
                }
            }
        }

        long ans = 0;
        for(int i=0; i<n; i++){
            ans += f ^ a[i];
        }

        System.out.println(ans);
    }
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> w(n);
    rep(i,n) cin >> w[i];

    vector<int> csum(n+1);
    csum[0] = 0;
    rep(i,n) csum[i+1] = csum[i] + w[i];

    int ans = INT_MAX;
    rep(i,n-1)
    {
        int wl = csum[i+1];
        int wr = csum[n]-wl;
        int tmp = abs(wr-wl);
        ans = min(ans, tmp);
    }

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

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;

#define rp(i,t) for(int i=0;i<(t);i++)
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rsp(i,s,t) for(int i=(s);i<(t);i++)
#define rrp(i,t,s) for(int i=(t);i>=(s);i--)
#define rcp(i,s,b,d) for(int i=(s);b;d)
#define mst(a,x) memset(a,x,sizeof(a))
#define INF 0x3f3f3f3f
#define N 100002

#define Dp puts("")
#define Dw printf
#define Ds printf("#")

typedef long long ll;
char ch;
int n,a[N],b[N],c[N],B,C;
ll s[N],ans;

inline void read(int &x){x=0;do{ch=getchar();}while(ch<'0'||'9'<ch);do{x=x*10+ch-'0';ch=getchar();}while('0'<=ch&&ch<='9');}

int main(void)
{
	read(n);
	rep(i,1,n)read(a[i]);sort(a+1,a+n+1);
	rep(i,1,n)read(b[i]);sort(b+1,b+n+1);
	rep(i,1,n)read(c[i]);sort(c+1,c+n+1);
	B=C=1;
	rep(i,1,n)
	{
		while(b[i]>=c[C]&&C<=n)C++;
		s[i]=s[i-1]+n-C+1;
	}
	rep(i,1,n)
	{
		while(a[i]>=b[B]&&B<=n)B++;
		ans+=s[n]-s[B-1];
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 2176
#include <stdio.h>

int main(void)
{
	static char p[10000001];
	int i, j;
	int n;
	
	for (i = 0; i < 10000001; i++){
		p[i] = 1;
	}
	p[0] = p[1] = 0;
	
	for (i = 2; i * i < 100000001; i++){
		if (p[i]){
			for (j = 2; j <= 10000000 / i; j++){
				p[i * j] = 0;
			}
		}
	}
	
	while (1){
		scanf("%d", &n);
		
		if (n == 0){
			break;
		}
		
		for (i = n; i >= 13; i--){
			if (p[i] && p[i - 2] && p[i - 6] && p[i - 8]){
			printf("%d\n", i);
			break;
			}
		}
	}
	
	return (0);
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

ll gcd(ll x, ll y){
    if(y == 0) return x;
    return gcd(y, x % y);
}

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

    ll res = 0;
    for (ll i = 0; i < K; ++i) {
        for (ll j = 0; j < K; ++j) {
            for (ll k = 0; k < K; ++k) {
                res += gcd(gcd(i+1, j+1), k+1);
            }
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
//#define DEBUG
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define deb(x) std::cout << #x << " " << x << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}
template<typename... T>
void write(T... a){
    ((cout << a << "\n"),...);
}

template<typename... T>
void write_space(T... a){
    ((cout << a << " "),...);
}

void solve(){
    string s;   
    cin >> s;
    int n = s.size();
    if( s[n-1] == 's'){
        s = s + "es";
    }else{
        s = s + "s";
    }
    cout << s << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    solve();
    return 0;
}



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

int main()
{

    string s,s2;
    cin>>s;
    s2=string(s.rbegin(),s.rend());

    int i=0,c=0;
    while(s2[i]!='\0'){

        if(s[i]!=s2[i]) c++;

        i++;
    }


    cout<<c/2<<endl;




        return 0;

}





Measured memory_bytes: 256
#include <iostream>

int gcd(int x, int y){
    if(x!=0 && y!=0){
        return (x>y) ? gcd(y,x%y) : gcd(x,y%x);
    }
    else{
        return x;
    }
}

int main(){

    int x,y;
    std::cin >> x >> y;
    std::cout << gcd(x,y) << '\n';

    return 0;
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
#define EM 100000000
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
LL LINF = 1e18;
int INF = 1e9;
using vint = vector<int>;
using vLL = vector<LL>;
using vvint = vector<vector<int>>;
using vvLL = vector<vector<LL>>;

bool solve(vint a, int b){
	bitset<16001> bit;
	bit[8000] = 1;
	for(auto d : a)	bit = (bit << d)|(bit >> d);
	if(b < 0) return 0; else return bit[b];
}
int main(){
	string s;
	int x, y;
	cin >> s; cin >> x >> y;
	vint X, Y;
	bool f = true;
	int start = 0;
	x += 8000, y += 8000;
	while(start < s.size() && s[start] == 'F'){
		x--;
		start++;
	}
	for(int i = start;i < s.size();i++){
		int d = 0;
		while(s[i] == 'F'){
			d++;
			i++;
			if(i == s.size())	break;
		}
		if(d > 0) {if(f)	X.push_back(d); else Y.push_back(d);}
		f = !f;
	}
	bool ans = solve(X, x) && solve(Y, y);
	if(ans)	cout << "Yes" << endl;	else cout << "No" << endl;
}

Measured memory_bytes: 256
import sys
from itertools import accumulate

n, *a = map(int, sys.stdin.read().split())

def main():
    ans = float('inf')
    left = 0; right = 2
    p = a[0]; q = 0; r = sum(a[1:3]); s = sum(a[3:])
    for c in range(1, n-2):
        q += a[c]; r -= a[c]
        while left < c - 1:
            nex = a[left+1]
            if abs((q - nex) - (p + nex)) <= abs(q - p):
                q -= nex; p += nex
                left += 1
            else:
                break  
        
        while right < n - 2:
            nex = a[right+1]
            if abs((s - nex) - (r + nex)) <= abs(s - r):
                s -= nex; r += nex
                right += 1
            else:
                break

        res = sorted([p, q, r, s])
        ans = min(ans, res[-1] - res[0])

    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 24996
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL INF=100000000000;
string u="abcdefghijklmnopqrstuvwxyz";


int main(){
    int N;
    cin >> N;
    LL H;
    cin >> H;
    LL a[N],b[N];
    for(int i=0;i<N;i++){
        cin >> a[i] >> b[i];
    }
    LL am=0;
    LL ans=0;
    sort(a,a+N);
    sort(b,b+N);
    am=a[N-1];
    for(int i=N-1;i>=0;i--){
        if(am<=b[i]){
            H-=b[i];
            ans++;
        }
        else break;
        if(H<=0){
            cout << ans << endl;
            return 0;
        }
    }
    while(0<H){
        H-=am;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}

int main() {
	int n;
	cin >> n;
	int num = n, div, sum = 0;
	while(num){
		div = num % 10;
		sum += div;
		num /= 10;
	}
	if(n % sum == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
import scala.io.StdIn

object Main {
  def main(args: Array[String]): Unit = {
    val inputs = Iterator.continually(StdIn.readLine()).takeWhile(_ != null)
    for{
      in <- inputs
      val Array(h, w, _*) = in.split(" ").map(_.toInt)
      }{
        if(h != 0 && w != 0){
          for{i <- 0 until h; j <- 0 until w}{
            if(i == 0 || i == h-1 || j == 0 || j == w-1) print("#")
            else print(".")
            if(j == w-1) println()
          }
          println()
        }
      }
  }
}

Measured memory_bytes: 56892
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Mid (l+r)/2
const int mod=1e9+7,inf=0x3f3f3f3f,maxn=1e5+5;
int n,m,Q,K;

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}



signed main(){
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);
    int x,y,z;
    x=read();y=read();z=read();
    if(x+y+z>=22)puts("bust");
    else puts("win");


    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char A = sc.next().charAt(0);
        char [] bi = new char[26];
        char [] sm = new char[26];
        char AA = 'A';
        char a = 'a';
        char anc = 'a';
        for(int i = 0;i < 26;i++){
            bi[i] = AA++;
            sm[i] = a++;
        }
        for(int i = 0;i < 26;i++){
            if(bi[i] == A){
                anc = 'A';
            }
        }
        System.out.println(anc);
    }
}

Measured memory_bytes: 35652
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <climits>
//#include <cmath>
//#include <algorithm>
using namespace std;

int main(void){
	int H,N;
	cin >> H >> N;
	vector<int> A(N),B(N);
	for(int i = 0; i < N; ++i){
		cin >> A[i] >> B[i];
	}
	vector<int> ans(H+1);
	ans[0] = 0;
	for(int i = 1; i < H + 1; ++i){
		ans[i] = INT_MAX;
	}
	for(int i = 1; i < H + 1; ++i){
		for(int j = 0;j < N; ++j){
			ans[i] = min(ans[i], B[j] + ans[max(i-A[j], 0)]);
		}
	}
	cout << ans[H];
}


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

int main() {
  int N,K;
  cin >> N >> K;
  int count = 0;
 
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    
    if (x >= K - x ) {
      count += K - x;
    }
    else {
      count += x;
    }
  }
  
  cout << count * 2 << endl;
}



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

// Inserted snippets: euclid, io, modint, root
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}
template<ll MOD = 1'000'000'007>
struct Mod {
	ll val;
	Mod() : val(0) {}
	Mod(ll xx) {
		if (0 <= xx && xx < MOD) val = xx;
		else val = (xx % MOD + MOD) % MOD;
	}
	Mod& operator+=(Mod b) { if ((val += b.val) >= MOD) val -= MOD; return *this; }
	Mod& operator-=(Mod b) { if ((val += MOD - b.val) >= MOD) val -= MOD; return *this; }
	Mod& operator*=(Mod b) { (val *= b.val) %= MOD; return *this; }
	Mod& operator/=(Mod b) { (val *= b.inv().val) %= MOD; return *this; }
	Mod operator+(Mod b) const { Mod<MOD> tmp(*this); return tmp += b; }
	Mod operator-(Mod b) const { Mod<MOD> tmp(*this); return tmp -= b; }
	Mod operator*(Mod b) const { Mod<MOD> tmp(*this); return tmp *= b; }
	Mod operator/(Mod b) const { Mod<MOD> tmp(*this); return tmp /= b; }
	Mod& operator++() { *this += 1; return *this; }
	Mod& operator--() { *this -= 1; return *this; }
	Mod operator++(int) { Mod<MOD> tmp(*this); operator++(); return tmp; }
	Mod operator--(int) { Mod<MOD> tmp(*this); operator--(); return tmp; }
	Mod inv() const {
		ll v, y, g = euclid(val, MOD, v, y);
		assert(g == 1); return Mod((v + MOD) % MOD);
	}
	Mod operator^(ll p) const {
		ll r = 1, b = val;
		for (; p; p >>= 1, b = b * b % MOD) if (p & 1) r = r * b % MOD;
		return Mod(r);
	}
	friend istream& operator>>(istream &is, Mod& mod) {
		ll tmp; is >> tmp;
		mod = Mod<MOD>(tmp);
		return is;
	}
	friend ostream& operator<<(ostream &os, const Mod& mod) {
		return os << mod.val;
	}
};
// End snippets

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  int n; read(n);
  string a, b; read(a, b);
  vector<int> q;
  for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) q.push_back(2), ++i;
    else q.push_back(1);
  }
  typedef Mod<> modint;
  modint ans = q[0] == 1 ? 3 : 6;
  rep(i, 1, sz(q)) {
    if (q[i - 1] == 1 && q[i] == 1)
      ans *= 2;
    else if (q[i - 1] == 1 && q[i] == 2)
      ans *= 2;
    else if (q[i - 1] == 2 && q[i] == 1)
      ans *= 1;
    else if (q[i - 1] == 2 && q[i] == 2)
      ans *= 3;
  }
  write(ans);
}


Measured memory_bytes: 3644
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define SIZE 2010
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
string s;
int main() {
	io(); cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(n) begin(n), end(n)
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts)
{
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v)
{
    for (auto &e : t)
        fill_v(e, v);
}

int main()
{
    int N;
    cin>>N;
    vector<ll> divisors(N+1); // divisors[i] := i の約数の個数
    for (ll i = 1; i < N+1; i++)
    {
        for (ll j = 1; j*i < N+1; j++)
        {
            divisors[i*j]++;
        }
        
    }
    ll ans=0;
    for (ll i = 1; i < N+1; i++)
    {
        ans += i * divisors[i];
    }
    
    cout<<ans;
    return 0;
}

Measured memory_bytes: 81392
if __name__ == '__main__':
    from collections import deque

    n = int(input())
    A = deque([])
    for i in range(n):
        command = input()
        if command[6] == "F":
            A.popleft()
        elif command[6] == "L":
            A.pop()
        elif command[0] == "i":
            A.appendleft(int(command[7:]))
        else:
            try:
                A.remove(int(command[7:]))
            except ValueError:
                continue

    print(*A)



Measured memory_bytes: 46060
N = int(input())

l = list()
for i in range(N):
    s, p = input().split()
    p = int(p)
    l.append([s, p, str(i+1)])

lup2 = sorted(l, key=lambda x:(x[0], -x[1]))
#print(lup2)

for i in range(len(lup2)):
    print(lup2[i][2])

Measured memory_bytes: 3060
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a,b;
    cin >> a >> b;
    cout << max(a+b, max(a-b,a*b));


    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<stdio.h>
int main(void)
{
  char buf[400002];
  int i = 0;
  while(1) if(EOF == (buf[++i] = getchar_unlocked())) break;
  int ans = 0;
  i >>= 1;
  char* x = buf + i;
  while(--i) ans += buf[i] != x[i];
  printf("%d", ans);
}


Measured memory_bytes: 1956
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {

	int H, W, K;
	cin >> H >> W >> K;
	vector<string> s(H);
	for (int i = 0; i < H; i++) {
		cin >> s[i];
	}

	int ans = 0;
	for (int is = 0; is < 1 << H; is++) {
		for (int js = 0; js < 1 << W; js++) {
			int cnt = 0;
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					if ((is >> i & 1) || (js >> j & 1)) continue;
					else if (s[i][j] == '#') cnt++;
				}
			}
			if (cnt == K) ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3624
#include<iostream>

using namespace std;
int main()
{
    int n,a[101];
    cin>>n;int sum=0;
    for(int i=0;i<n;i+=1){
        cin>>a[i];
        sum = sum+a[i];
    }
    int s;
    sum = sum/n;
    s = sum+1;int s1,s2=0,k;
    for(int i=0;i<n;i+=1){
           s1 = a[i]-sum;
           k = s1*s1;
           s2 = s2+k;
    }
    int s3=0;
    for(int i=0;i<n;i+=1){
           s1 = a[i]-s;
           k = s1*s1;
           s3 = s3+k;
    }
    if(s3>s2) cout<<s2<<endl;
    else cout<<s3<<endl;


    return 0;
}


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

int main(){
  int a,p;
  cin >>a>>p;
  cout<<(a*3+p)/2<<endl;
}



Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)] 
M = int(input())
T = [input() for _ in range(M)] 

Sw = list(set(S))
Tw = list(set(T))

mm = 0
for i in Sw:
    tmp = S.count(i) - T.count(i)
    if mm < tmp:
        mm = tmp

for i in Tw:
    tmp = S.count(i) - T.count(i)
    if mm < tmp:
        mm = tmp

print(mm)

Measured memory_bytes: 3064