akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include <stdio.h>
#include<map>
//#include<set>
//#include<vector>
//#include<iomanip>
using namespace std;
int main(){

    long long n,ans=0;
    cin>>n;
    map<string,long long>arr;
    char x[11];
    for(int i=0;i<n;i++){
        cin>>x;
        sort(x,x+10);
        arr[x]++;
        ans+=arr[x]-1;
    }
    cout<<ans;
    return 0;
}



Measured memory_bytes: 11304
using System;

class Atcoder80
{
    public static void Main()
    {
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());
        int c = int.Parse(Console.ReadLine());
        int d = int.Parse(Console.ReadLine());

        if (a <= b && c <= d)
            Console.WriteLine(a + c);
        else if (a <= b && c > d)
            Console.WriteLine(a + d);
        else if (a > b && c <= d)
            Console.WriteLine(b + c);
        else
            Console.WriteLine(b + d);
    }
}

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


int main(void){
    vector<int> a;
    rep(i,3){
        int x;
        cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    int ans = 0;
    ans += abs(a[2]-a[1]) + abs(a[1]-a[0]);
    cout <<ans <<endl;
    
    
    return 0;
}





















































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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

template<typename T>
struct BIT {
    vector<T> array;
    int n;

    BIT(int n) : array(n+1, 0), n(n) {}

    void init() {
        rep(i, n) array[i] = 0;
    }

    T sum(int i) {
        T s = 0;
        while (i > 0) {
            s += array[i];
            i -= i&-i;
        }
        return s;
    }

    T sum(int l, int r) {
        T ls = sum(l-1);
        T rs = sum(r);
        return rs - ls;
    }

    void add(int i, T x) {
        while (i <= n) {
            array[i] += x;
            i += i&-i;
        }
    }

};

int offset = 100000;
int N, A[101010];
BIT<int> bit(201010);

int check(int x) {
    bit.init();

    ll sm = 0;
    int tot = 0;
    bit.add(offset, 1);
    rep(i, N) {
        if (x <= A[i]) tot++;
        else tot--;

        sm += bit.sum(1, tot+offset);
        bit.add(tot+offset, 1);
    }

    return (1LL * N * (N-1) / 2 + N + 1) / 2 <= sm;
}

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

    cin >> N;
    int ng = 0, ok = 1e9+1;
    rep(i, N) {
        cin >> A[i];
        ng = max(ng, A[i]);
        ok = min(ok, A[i]);
    }

    ok--; ng++;
    while (ok+1 != ng) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }

    cout << ok << endl;
}


Measured memory_bytes: 1408
from sys import stdin
from collections import defaultdict
readline = stdin.readline



def main():
    x, y, e = map(int, readline().split())
    g = defaultdict(list)
    residual = [[0] * (x + y + 2) for _ in range(x + y + 2)]
    source, sink = x + y, x + y + 1
    # source->x
    for xi in range(x):
        g[source].append(xi)
        residual[source][xi] = 1
    # y->sink
    for yi in range(x, x + y):
        g[yi].append(sink)
        residual[yi][sink] = 1
    # x <-> y
    for _ in range(e):
        s, t = map(int, readline().split())
        t += x
        g[s].append(t)
        g[t].append(s)
        residual[s][t] = 1

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow
    print(sum(residual[sink]))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()

Measured memory_bytes: 7572
package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
    "strconv"
    // "sort"
    // "regexp"
)

const (
    initialBufSize = 10000
    maxBufSize = 1000000
)
var reader = bufio.NewReaderSize(os.Stdin, maxBufSize)
var writer = bufio.NewWriter(os.Stdout)

func main() {
    var r string
    r = readLine()
    var n = s2i(r)
    ios := strAry2intAry(split(readLine()))
    fmt.Println(calc(ios, n))
}

func calc(g []int, n int) int {
    var del int
    var next int
    var i int
    next = 1
    for i=0;i<n;i++ {
        if g[i] == next {
            next++
        } else {
            del++
        }
    }
    // このとき数列全部一緒
    if n == del {
        del = -1
    }
    return del
}

func write(s string) {
    writer.WriteString(s)
}

func print() {
    writer.Flush()
}

func readLine() string {
    buf := make([]byte, 0, maxBufSize)
    for {
        l, p, e := reader.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    return string(buf)
}

func s2i(s string) int {
    var intVal,e = strconv.Atoi(s)
    if e != nil {
        panic(e)
    }
    return intVal
}

func i2s(i int) string {
    return string(i)
}

func s2f(s string) float64 {
    var floatVal,e = strconv.ParseFloat(s, 64)
    if e != nil {
        panic(e)
    }
    return floatVal
}

func sum(i []int) int {
    sum := 0
    for _,val := range i {
        sum += val
    }
    return sum
}

func split(s string) []string {
    return strings.Fields(s)
}

func strAry2intAry(strs []string) []int {
    var ret = make([]int, 0, len(strs))
    for _ , str := range strs {
        var intVal, e = strconv.Atoi(string(str));
        if e != nil {
            panic(e)
        }
        ret = append(ret, intVal)
    }
    return ret
}

func intAry2strAry(nums []int) []string {
    var ret = make([]string, 0, len(nums))
    for _ , num := range nums {
        var strVal = strconv.Itoa(num);
        ret = append(ret, strVal)
    }
    return ret
}

func ary2str(strs []string) string {
    return strings.Join(strs, " ")
}

func reverse(res []int) []int {
    for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
    return res
}

//  
// func regexpExample() {
//     // Your code here!
//     var str = "13:20"
//     r := regexp.MustCompile(`(\d+):(\d+)`)
//     fmt.Println(r.FindStringSubmatch(str))
// }


// type Country struct {
//     gold int
//     silver int
//     blonze int
// }

// // 複数ソートのサンプル
// func stableSortExample() []Country{
//     var country = []Country {
//         {gold:1, silver:2, blonze:3},
//         {gold:1, silver:2, blonze:3},
//         {gold:1, silver:3, blonze:2},
//         {gold:1, silver:3, blonze:3},
//     }
//     sort.SliceStable(country, func(i, j int) bool { return country[i].blonze > country[j].blonze })
//     sort.SliceStable(country, func(i, j int) bool { return country[i].silver > country[j].silver })
//     sort.SliceStable(country, func(i, j int) bool { return country[i].gold > country[j].gold })
//     return country
// }

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

using namespace std;

#define ll long long
#define mx 0
#define mn 1e9
#define v(dt) vector<dt>
#define pr(x, y) pair<x,y>
#define loop(x, s, n) for(int x = s; x < n; ++x)
#define in_arr(n) loop(i,0,n){cin>>a[i];}
#define out_arr(n) loop(i,0,n){cout<<a[i];}

const int N = 1e5 + 7;

inline void boost() {
    cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
}

//int a[N];

int main() {
    boost();
    ll n;
    cin>>n;
    ll res = 1e18;

    for (int i = 1;i<= sqrt(n); i++) {
        if (n % i == 0)
        {
            res = min(res,(i+(n/i))-2);
        }
    }
    cout<<res;

}

Measured memory_bytes: 256
use std::cmp::Ord;
use std::cmp::Ordering;
use std::cmp::PartialOrd;
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    // (city name, rating, index)
    let mut sp: Vec<(String, Reverse<i32>, usize)> = (0..n).map(|i| (read(), Reverse(read()), i + 1)).collect();

    sp.sort();

    for &(_, _, index) in sp.iter() {
        println!("{}", index);
    }
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

#[derive(PartialEq, Eq, Debug, Copy, Clone, Default, Hash)]
struct Reverse<T>(T);

impl<T: PartialOrd> PartialOrd for Reverse<T> {
    #[inline]
    fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Reverse<T> {
    #[inline]
    fn cmp(&self, other: &Reverse<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define int long long 
#define LL long long 
#define LD long double
#define PI 3.14159265358979323846
#define MOD ((LL)1e9+7)
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

			
int32_t main()
{
	IOS
	int n=5,mn=1e18;
	vector<int>A(n),B(n);
	for(int i=0;i<5;i++)
	{
		cin>>A[i];
		B[i]=i;
	}
	do
	{
		int t=0;
		for(int i=0;i<n;i++)
		{
			t+=(10-t%10)%10;
			t+=A[ B[i] ];
		}
		mn=min(mn,t);
	}while(next_permutation(B.begin(),B.end()));
	
	cout<<mn<<endl;
	
}
	

	
		


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9000000000000000000
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)

vector<vi> e,p;
vi _,d,vis;
ll r,_ig;

ll dist(ll v){
  if (v == r) return d[v] = 0;
  if (d[v] != -1) return d[v];
  ll rs = 0;
  trav(u,p[v]) rs = max(dist(u)+1,rs);
  return d[v] = rs;
}

int main(){
  ios::sync_with_stdio(0);
  ll n,m,a,b; cin >> n >> m;
  e.assign(n,_);
  p.assign(n,_);
  rep(i,0,n+m-1){
    cin >> a >> b; a--; b--;
    e[a].push_back(b);
    p[b].push_back(a);
  }
  rep(i,0,n) if (sz(p[i]) == 0) r = i;
  d.assign(n,-1);
  rep(i,0,n) _ig = dist(i);
  rep(i,0,n){
    ll v = i;
    trav(u,p[v]){
      if (d[u] != d[v]-1) continue;
      cout << u+1 << endl;
    }
    if (sz(p[v]) == 0) cout << 0 << endl;
  }
}


Measured memory_bytes: 15488
#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define PI 3.14159265358979
	#define EPS 1e-8
	#define mod 
	#define fi first
	#define se second
	#define mp make_pair
	#define pb push_back
	#define endl "\n"
		 
	const ll INF=1e15;	
	const int N=2e5+50;
	 

	 
	long long binpow(long long a, long long b, long long m) {
		a %= m;
		long long res = 1;
		while (b > 0) {
			if (b & 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	
	
	int main()
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);cout.tie(0);
		
		ll n;
		cin>>n;
		
		vector<ll> a(n+1),b(n+1);
		vector<ll> v1,v2;
		for(ll i=1;i<=n;i++)
		{
			cin>>a[i]>>b[i];
			v1.pb(a[i]);
			v2.pb(b[i]);
		}
		
		sort(v1.begin(),v1.end());
		
		sort(v2.begin(),v2.end());
		
		if(n%2==1)
		{
			ll lo=v1[n/2];
			ll hi=v2[n/2];
			
			cout<<(hi-lo+1);
		}
		else
		{
			ll lo=v1[n/2-1];
			ll hi=v1[n/2];
			
			ll l1=(hi+lo);
			
			lo=v2[n/2];
			hi = v2[n/2-1];
			
			ll l2=(hi+lo);
			
	
			cout<<(l2-l1+1)<<endl;
			
		}
		
		
		
	}
		
		
	


Measured memory_bytes: 9812
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree < pairs ,  null_type , greater<pairs>,  rb_tree_tag ,  tree_order_statistics_node_update > 
#define ll long long
#define lld long double
#define vc vector<ll>
const ll MOD=(1e9 +7);
typedef pair<ll,ll>pairs;
ll power(ll a, ll b){ll res=1;a=a%MOD;while(b>0){if(b&1){res=(res*a)%MOD;b--;}a=(a*a)%MOD;b>>=1;}
    return res;}

int main() {
	// your code goes here
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	ll t,n,i,j,k,c,f;
	cin>>n; vc a(n+1);
	for(i=1;i<=n;i++)cin>>a[i];
	vc prefix(n+1);
	prefix[n]=a[n];
	for(i=n-1;i>=1;i--){
	    prefix[i]=prefix[i+1]+a[i];
	}
	ll sum=0;
	for(i=1;i<n;i++)
	{
	    sum+=a[i]*(prefix[i+1]%MOD);
	    sum%=MOD;
	}
	cout<<sum;
	return 0;
}


Measured memory_bytes: 6340
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

const int MAX = 3500;

struct UnionFind
{
	vector<int> p;
	UnionFind(int n) :p(n) {
		for (int i = 0; i < n; i++) {
			p[i] = i;
		}
	}

	int root(int x) {
		int px = p[x];
		if (px == x) {
			return x;
		}

		p[x] = root(px);
		return p[x];
	}

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) {
			return;
		}

		p[rx] = ry;
	}
};

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


	UnionFind uf(n + m);
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int l;
			cin >> l;
			l--;
			uf.unite(i + m, l);
		}
	}

	int r = uf.root(m);
	for (int i = 0; i < n; i++) {
		if (uf.root(i + m) != r) {
			cout << "NO" << endl;
			return 0;
		}
	}

	cout << "YES" << endl;

}

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

#define REP(i,n) for(int i=0;i<(int)n;i++)
#define REP1(i,j,n) for(int i=j;i<(int)n;i++)
#define pb(x) push_back(x)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define double long double
#define mp(x,y) make_pair(x,y)

typedef long long ll;

using namespace std;

int s(int n){
    int r=0;
    while(n){
        r+=n%10;
        n/=10;
    }
    return r;
}
int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("in.txt","r",stdin);
    // #endif
        
    int n;
    cin>>n;
    int mn=100000000;
    REP1(i,1,n){
        mn=min(mn,s(i)+s(n-i));
    }
    cout<<mn<<"\n";
    
    return 0;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
s=[]
p=0
for i in range(h):
    t=list(input())
    p+=t.count("#")
    s.append(t)
t=[[0]*w for i in range(h)]
t[0][0]=1
u=[(0,0)]
while u:
    (x,y)=u[0]
    for i,j in [(0,-1),(0,1),(-1,0),(1,0)]:
        xx=x+i
        yy=y+j
        if (xx!=-1 and xx!=h and yy!=-1 and yy!=w):
            if s[xx][yy]=="."and t[xx][yy]==0:
                u.append((xx,yy))
                if t[xx][yy]==0:
                    t[xx][yy]+=t[x][y]+1
                else:
                    t[xx][yy]+=min(t[xx][yy],t[x][y]+1)
    u.pop(0)
if t[h-1][w-1]==0:
    print(-1)
else:
    print(h*w-p-t[h-1][w-1])
            
        
        

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

long long nn;
long long  ans;
int c = 0;

int main(){
    cin >> nn;
    //cout << (int)nn << endl;
    for(long long i = 1; i * i <= nn; i++){
        if(nn % i == 0){
            ans = i;
        }
    }
    //cout << ans << endl;
    if(ans > nn / ans){
        while(ans > 0){
            ans = ans / 10;
            c++;
        }
        cout << c << endl;
    }else{
        ans = nn / ans;
        while(ans > 0){
            ans = ans / 10;
            c++;
        }
        cout << c << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
int n, ans;
double d;
double x, y;
int main() {
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		cin >> x >> y;
		if (d - sqrt(x * x + y * y) >= 0) {
			ans++;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3840
from fractions import gcd


def main():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    for i in range(n):
        a[i] =abs(a[i] - x)
 
    ans = 0
    for aa in a:
        ans = gcd(aa, ans)
    print(ans)

    
if __name__ == '__main__':
    main()

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

#define ll long long

using namespace std;

void scan() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}


const int maxn = 1e6 + 7;

struct node {
    int to, next, v;
} a[100007];
int head[maxn], cnt, dis[maxn], vis[maxn], f[maxn];
queue<int> q;
char s[maxn];

void add(int x, int y, int v) {
    a[++cnt].next = head[x];
    a[cnt].to = y;
    a[cnt].v = v;
    head[x] = cnt;
}

void dfs(int x, int c) {
    vis[x] = c;
    for (int i = head[x]; i; i = a[i].next) {
        int v = a[i].to;
        if (vis[v] == -1) dfs(v, c ^ 1);
        else if (vis[v] != (c ^ 1)) {
            cout << -1 << endl;
            exit(0);
        }
    }
}

void spfa(int s) {
    q.push(s);
    memset(dis, 1, sizeof(dis));
    f[s] = 1, dis[s] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        f[now] = 0;
        for (int i = head[now]; i; i = a[i].next) {
            int v = a[i].to;
            if (dis[v] > dis[now] + a[i].v) {
                dis[v] = dis[now] + a[i].v;
                if (!f[v]) {
                    q.push(v);
                    f[v] = 1;
                }
            }
        }
    }
}

int main() {
    int n = 0, mx = 0, x;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s + 1;
        for (int j = 1; j <= n; j++) {
            if (s[j] - '0' == 1) add(i, j, 1);
        }
        vis[i] = -1;
    }
    dfs(1, 0);
    for (int j = 1; j <= n; j++) {
        spfa(j);
        for (int i = 1; i <= n; i++) mx = max(mx, dis[i]);
    }
    cout << mx + 1 << endl;
    return 0;
}


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

int main(){
    int n, y;
    cin >> n >> y;
    /*
    10000*a + 5000*b + 1000*c = y
    a + b + c = n
    a = 0 to n
    b = 0 to n-a
    c = n-a-b
    */
   int a, b, c;
   bool ret = false;
   tuple<int,int,int> ans;
   for(a=0; a<=n; a++){
       for(b=0; b<=n-a; b++){
           c = n-a-b;
           ret |= 10000*a+5000*b+1000*c==y;
           if(ret) break;
       }
       if(ret) break;
   }
   if(ret) cout << a << " " << b  << " " << c << endl;
   else cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int a,b,aa=0,bb=0;
	for(int i=0;i<4;i++){
		cin>>a;
		aa+=a;
	}
	for(int i=0;i<4;i++){
		cin>>b;
		bb+=b;
	}
	cout<<max(aa,bb)<<endl;
	return 0;
}

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

struct dice {
	int back, bottom, front, left, right, top;
};

int main() {
	dice a;
	cin >> a.top >> a.front >> a.right >> a.left >> a.back >> a.bottom;
	int q, b, c;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> b >> c;
		if (a.bottom == b && a.left == c || a.left == b && a.top == c || a.right == b && a.bottom == c || a.top == b && a.right == c) cout << a.back;
		else if (a.back == b && a.right == c || a.front == b && a.left == c || a.left == b && a.back == c || a.right == b && a.front == c) cout << a.bottom;
		else if (a.bottom == b && a.right == c || a.left == b && a.bottom == c || a.right == b && a.top == c || a.top == b && a.left == c) cout << a.front;
		else if (a.back == b && a.bottom == c || a.bottom == b && a.front == c || a.front == b && a.top == c || a.top == b && a.back == c) cout << a.left;
		else if (a.back == b && a.top == c || a.bottom == b && a.back == c || a.front == b && a.bottom == c || a.top == b && a.front == c) cout << a.right;
		else cout << a.top;
		cout << endl;
	}
}


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

using namespace std;

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

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

	cout<<d[n/2]-d[n/2-1]<<endl;
	return 0;
}

Measured memory_bytes: 640
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($($args),*), ($($args),*));
    };
}

const M: usize = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let m: usize = sc.cin();

    let mut ps = vec![];
    let mut c = vec![false; n + 10];
    let mut d = vec![false; n + 10];

    for i in 0..m {
        let a: usize = sc.cin();
        let b: usize = sc.cin();
        ps.push((a, b));
        if a == 1 {
            c[b] = true;
        }
    }
    // trace!(c);
    for i in 0..m {
        let (a, b) = ps[i];
        if c[a] {
            d[b] = true;
        }
    }
    // trace!(d);
    println!("{}", if d[n] { "POSSIBLE" } else { "IMPOSSIBLE" });
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
    fn get_char(&mut self) -> char {
        self.reserve();
        let head = self.buffer[0].chars().nth(0).unwrap();
        let tail = String::from( &self.buffer[0][1..] );
        if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.pop_front(); }
        head
    }
}


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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> ls(n,0);
  for (int i = 0; i < k; i++){
    int d;
    cin >> d;
    for (int j = 0; j < d; j++){
      int a;
      cin >> a;
      ls.at(a-1)++;
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++){
    if (ls.at(i) == 0){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
const int mod = 1000000007;
const int max_n = 200005;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(max_n);


int main(){
    ll n;cin >> n;
    vl v(n-1);
    ll pre=0;
    rep(i,n){
        if(!i)cin >> pre;
        else{
            ll a;cin >> a;
            v[i-1]=a-pre;
            pre=a;

        }
    }
    mint ans=0;
    mint cus=0;
    rep(i,n-1){
        cus+=comb.fact[n-1]/(i+1);
        ans+=cus*v[i];
    }
    cout << ans <<endl;
}

Measured memory_bytes: 4096
#include <stdio.h>
 
int main(void) {
    int a;
    int b;
    int result;

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

    result = (a * b) % 2;
    if (result == 0) {
        printf("Even");
    }
    else {
        printf("Odd");
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n;
  cin >> n;
  vector<P> vec[n];
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    for (int j = 0; j < a; ++j) {
      int x, y;
      cin >> x >> y;
      x--;
      vec[i].push_back(P(x, y));
    }
  }
  int ans = 0;
  for (int bit = 0; bit < (1 << n); ++bit) {
    int cnt = 0;
    vector<bool> vec2(n, false);
    for (int i = 0; i < n; ++i) {
      if (bit >> i & 1) {
        cnt++;
        vec2[i] = true;
      }
    }
    bool ok = true;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < vec[i].size(); ++j) {
        int xx = vec[i][j].first;
        int yy = vec[i][j].second;
        if (vec2[i]) {
          if (vec2[xx] != yy) ok = false;
        }
      }
    }
    if (ok) {
      ans = max(ans, cnt);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define sqr(a) a*a


using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> pi;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, k;
    cin >> n >> k;
    vi a(n);
    for(auto &el : a){
        cin >> el;
    }
    sort(a.begin(), a.end());
    ll sum = 0;
    for(int i = 0; i < n-k; ++i){
        sum += a[i];
    }
    cout << sum;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,k,g,i=1,x,t;
int main()
{
    scanf("%d%d%d",&n,&k,&g); t=g; for (;i<n;i++) {scanf("%d",&x); t=max(t,x); g=__gcd(g,x);}
    if (k%g||k>t) puts("IMPOSSIBLE"); else puts("POSSIBLE");
}

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

typedef unsigned long long ull;

#define REP(i, N) for (int i = 0; i < N; i++)
#define ANS(a) cout << a << endl;
#define SORT(V) sort(V.begin(), V.end())
#define RSORT(V) sort(V.rbegin(), V.rend())

#define DBG(V) for (auto v : V) cout << v << " "; cout << endl

int N, L;

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

  int ans = 0;
  REP(i, N) {
    ans += L + i;
  }
  if (0 < L) {
    ans -= L;
  }
  if (L < 0 && L + N <= 0) {
    ans -= L + N - 1;
  }

  ANS(ans);
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){

	int A,B;

	scanf("%d %d",&A,&B);

	if(A%3==0||B%3==0||(A+B)%3==0){
	printf("Possible\n");
	}
	else{
	printf("Impossible\n");
	}

	return 0;
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-

s = input()

ans = ''

for i in range(len(s)-1):
    if s[i] == s[i+1]:
        ans = ' '.join([str(i+1), str(i+2)])
for j in range(len(s)-2):
    if s[j] == s[j+2]:
        ans = ' '.join([str(j+1), str(j+3)])

if ans:
    print(ans)
else:
    print('-1 -1')


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

const int A = 1000005;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> c(A);
  rep(i,n) {
    cin >> a[i];
    c[a[i]]++;
  }

  bool pairwise = true;
  for (int i = 2; i < A; i++) {
    int cnt = 0;
    for (int j = i; j < A; j += i) {
      cnt += c[j];
    }
    if (cnt > 1) pairwise = false;
  }

  if (pairwise) {
    cout << "pairwise coprime" << endl;
    return 0;
  }

  int g = 0;
  rep(i,n) g = gcd(g,a[i]);
  if (g == 1) {
    cout << "setwise coprime" << endl;
    return 0;
  }

  cout << "not coprime" << endl;
  return 0;
}

Measured memory_bytes: 11184
def f():
    N, M = map(int, input().split(" "))
    S = {}
    for _ in range(M):
        s, c = map(int, input().split(" "))
        if S.get(s) is not None and S.get(s) != c:
            return -1
        S[s] = min([S.get(s, 10000), c])

    l = []
    for i in range(1000):
        str_i = str(i)
        if len(str_i) != N:
            continue

        flag = all([
            int(str_i[k - 1]) == v
            for k, v in S.items()
        ])
    
        if flag:
            l.append(i)

    if not l:
        return -1
    
    return min(l)

print(f())


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



int main() {
  int x,a;
  cin >> x >> a;
  string ans = x < a ? "0" : "10";
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
//入出力等基本
#include <iostream>
#include <vector>
#include <map>
#include <string>

#define 中心() main()
#define 返 return
#define 入力(a) cin >> a
#define 出力(a) cout << a << endl
#define 再帰(s,t) for(整数 s = 0; s < 整数(t); s += 1)
#define 如果(a) if(a)
#define 場合(a) while(a)
#define 先(a) a.first
#define 後(a) a.second
#define 自動 auto
#define 定数 const
#define 部分文字列(m,s,t) m.substr(s,t)
#define 測長(a) a.length()

using namespace std;

typedef int 整;
typedef void 無;
typedef long long 整数;
typedef vector<整数> 整数配列;
typedef map<整数,整数> 整辞書;
typedef string 文字列;

整 中心(){
    文字列 m;
    入力(m);
    出力(部分文字列(m,0,測長(m)-8));
    返 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[1919];
int main(){
	int n,x;
	cin>>n>>x;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int ans=0;
	for(int i=0;i<n;i++){
		if(x>=a[i]){
		x-=a[i];
		ans++;
		}
		else{break;}
	}
	if(x>0&&n==ans){ans--;}
	cout<<ans<<endl;
}
	
	


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> l(n);
    for(int i=0; i<n; i++){
        cin >> l.at(i);
    }
    sort(l.begin(), l.end(), greater<int>());
    int count = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(l.at(i) == l.at(j)){
                continue;
            }
            for(int k=j+1; k<n; k++){
                if(l.at(i) == l.at(k) || l.at(j) == l.at(k)){
                    continue;
                }
                if(l.at(i) < l.at(j) + l.at(k)){
                    count++;
                }else{
                    break;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#define ll long long
using namespace std;
int main()
{
    ll K;
    while(scanf("%lld",&K)!=EOF)
    {
        printf("50\n");
        for(int i=0; i<50; i++)
        {
            if(i<K%50)
            {
                if(i==0)
                {
                    printf("%lld",K/50+50);
                }
                else
                {
                    printf(" %lld",K/50+50);
                }
            }
            else
            {
                if(i==0)
                {
                    printf("%lld",K/50+50-K%50-1);
                }
                else
                {
                    printf(" %lld",K/50+50-K%50-1);
                }
            }
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
  int n;
  string s;
  cin >> n >> s;
  int i, j, k;
  long r = 0;
  long g = 0;
  long b = 0;
  for (i = 0; i < n; i++) {
    if (s[i] == 'R') r++;
    else if (s[i] == 'G') g++;
    else if (s[i] == 'B') b++;
  }
  long long w = 0;
  for (i = 0; i < n - 2; i++) {
    for (j = i + 1; j < n - 1; j++) {
      k = j - i + j;
      if (k >= n) continue;
      if (s[i] != s[j] & s[j] != s[k] & s[k] != s[i]) w++;
    }
  }
  cout << r * g * b - w << endl;
  return 0;
}


Measured memory_bytes: 3612
#include<stdio.h>

int search(int A[],int n,int key){
  int i=0;
  A[n]=key;
  while(A[i]!=key) i++;
  return i!=n;
}

int main(){
  int i,n,A[10000+1],q,key,sum=0;

  scanf("%d",&n);

  for(i=0;i<n;i++) scanf("%d",&A[i]);

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(search(A,n,key)) sum++;
  }

  printf("%d\n",sum);
  return 0;
}



Measured memory_bytes: 2076
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
  int R[MAX], n;

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> R[i];
  }

  int maxv = -2000000000;
  int minv = R[0];

  for (int i = 1; i < n; i++) {
    maxv = max(maxv, R[i] - minv);
    minv = min(minv, R[i]);
  }

  cout << maxv << endl;

  return 0;
}



Measured memory_bytes: 3852
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
typedef long long ll;
typedef long double ld;
using namespace std;

int main(void){
    int S, W;
    cin >> S >> W;
    cout << (S<=W ? "unsafe" : "safe") << endl;
    return 0;
}


Measured memory_bytes: 3632
from sys import stdin,stdout
from collections import defaultdict
def bfs(src):
    q=[src]
    par=[-1]*(n+1)
    vis=[0]*(n+1)
    ans=[]
    while q:
        cur=q.pop(0)
        for neigh in g[cur]:
            if not vis[neigh]:
                vis[neigh]=1
                q+=[neigh]
                par[neigh]=cur
    for i in range(2,n+1):
        if par[i]==-1:
            print('No')
            return
        ans+=[par[i]]
    print('Yes')
    for v in ans:
        print(v)
for i in range(1):#int(stdin.readline())):
    # n=int(stdin.readline())
    g=defaultdict(list)
    n,e=list(map(int,stdin.readline().split()))
    for _ in range(e):
        a,b=map(int,stdin.readline().split())
        g[a]+=[b]
        g[b]+=[a]
    bfs(1)

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

int main() {
  int N,L;
  cin >> N>>L;
  vector<string> S(N);
  rep(i,N) {
    string s;
    cin >>s;
    S.at(i) = s;
  }

  sort(S.begin(),S.end());
  string min_S;
  for(auto x:S) {
    min_S += x;
  }
  cout << min_S << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        LinkedList<Integer>[] edges = new LinkedList[n+1];
        for(int i = 0; i < n+1; i++) edges[i] = new LinkedList<Integer>();
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(f.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }
        boolean[] seen = new boolean[n+1];
        int[] dists = new int[n+1];
        int[] par = new int[n+1];
        LinkedList<State> q = new LinkedList<State>();
        q.add(new State(1,  -1, 0));
        while(!q.isEmpty()){
            State s = q.poll();
            if(seen[s.node]) continue;
            seen[s.node] = true;
            dists[s.node] = s.dist;
            par[s.node] = s.par;
            for(int e: edges[s.node]) q.add(new State(e, s.node, s.dist+1));
        }
        out.println("Yes");
        for(int i = 2; i <= n; i++){
            out.println(par[i]);
        }




        out.close();
    }
    static class State{
        public int node;
        public int dist;
        public int par;
        public State(int n, int p, int d){
            node=n;
            dist=d;
            par=p;
        }
    }
}


Measured memory_bytes: 87712
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
  
int main()
{
  string S;
  ll K;
  cin >> S >> K;
  int flag = 0;
  REP(i,S.size()){
    if(S.at(i) != '1'){
      if(i<K){
        cout << S.at(i) << endl;
      }else{
        cout << 1 << endl;
      }
      flag = 1;
      break;
    }
  }
  if(flag == 0){
    cout << 1 << endl;
  }
}

Measured memory_bytes: 3596
a, b, c, d = list(map(int, input().strip().split()))
ab = [a,b]
cd = [c,d]
xy = a*c

abcd = [a,b,c,d]

for i in range(2):
    for j in range(2):
        if ab[i]*cd[j] > xy:
            xy = ab[i]*cd[j]

print(xy)

Measured memory_bytes: 9188
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
        int k = sc.nextInt();
        int ans = 1;
        while(n >= k){
        	n /= k;
            ans++;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35684
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x)  ((x) * (x)) 
#define cub(x)  ((x) * (x) * (x))
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; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main() {
  int n,m; cin >> n >> m;
  if(n>m) swap(n,m);

  FOR(i,0,m-1) cout << n;
  cout << endl;
}

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

using namespace std;

const int MOD = 1000000007;

int main(){
    string S;
    while(cin >> S){
        vector<vector<long long>> dp(S.size()+1, vector<long long>(2, 0));
        dp[0][0] = 1;
        for(int i=0;i<S.size();i++){
            if(S[i] == '0'){
                dp[i+1][0] = dp[i][0];
                dp[i+1][1] = 3 * dp[i][1] % MOD;
            } else {
                dp[i+1][0] = 2 * dp[i][0] % MOD;
                dp[i+1][1] = (dp[i][0] + 3 * dp[i][1]) % MOD;
            }
        }
        cout << ((dp.back()[0] + dp.back()[1])%MOD) << endl;
    }
}

Measured memory_bytes: 5760
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main
{
	public static void main(String args[])throws IOException {
		BufferedReader br  =new BufferedReader(new InputStreamReader(System.in));
		int n =Integer.parseInt(br.readLine());
		long a[]=new long[0];
		a=Arrays.stream(br.readLine().split("\\s+")).mapToLong(Long::parseLong).toArray();
	    PriorityQueue<Long> npq = new PriorityQueue<>(Comparator.naturalOrder());
	    PriorityQueue<Long> rpq = new PriorityQueue<>(Comparator.reverseOrder());
	    long[] s = new long[n+1];
	    long[] t = new long[n+1];
	    long su = 0L;
	    long tu = 0L;
	    for (int i=0;i<n;i++) {
	      npq.offer(a[i]);
	      su += a[i];
	      rpq.offer(a[3*n-1-i]);
	      tu += a[3*n-1-i];
	    }
	    s[0] = su;
	    t[n] = tu;
	    for (int i=n;i<2*n;i++) {
	      npq.offer(a[i]);
	      su += a[i]-npq.poll();
	      s[i-n+1] = su;
	      rpq.offer(a[3*n-1-i]);
	      tu += a[3*n-1-i]-rpq.poll();
	      t[2*n-i-1] = tu;
	    }
	    long m = s[0]-t[0];
	    for (int i=0;i<n+1;i++) {
	      if (m < s[i]-t[i]) m = s[i]-t[i];
	    }
	    System.out.println(m);
	
	}
}

Measured memory_bytes: 95656
// ABC161E - Yutori

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

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

	vector<int> early, late;

	for (int i = 0; i < N; i++) {
		if (S[i] == 'o') {
			early.push_back(i);
			if (early.size() == K) {
				break;
			}
			i += C;
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		if (S[i] == 'o') {
			late.push_back(i);
			if (late.size() == K) {
				break;
			}
			i -= C;
		}
	}
	sort(late.begin(), late.end());

//	for (int i = 0; i < K; i++) {
//		cout << early[i] << " " << late[i] << endl;
//	}

	for (int i = 0; i < K; i++) {
		if (early[i] == late[i]) {
			cout << early[i] + 1 << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3448
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#include <random>

#define ff first
#define ss second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define MOD 998244353LL

pii operator+(pii a, pii b)
{
    return { a.ff + b.ff,a.ss + b.ss };
}

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

    int n, q;
    cin >> n >> q;
    ll answer = (ll)(n - 2) * (ll)(n - 2);
    vector<pii> v = { {n,n} }, h = { {n,n} };
    while (q--) {
        int a, b;
        cin >> a >> b;
        if (a == 1) {
            auto ret = lower_bound(v.rbegin(), v.rend(), make_pair(b, 0));
            if (ret == v.rbegin()) {
                v.push_back({ b,h.back().ff });
                answer -= h.back().ff - 2;
            }
            else {
                ret--;
                answer -= ret->ss - 2;
            }
        }
        else {
            auto ret = lower_bound(h.rbegin(), h.rend(), make_pair(b, 0));
            if (ret == h.rbegin()) {
                h.push_back({ b,v.back().ff });
                answer -= v.back().ff - 2;
            }
            else {
                ret--;
                answer -= ret->ss - 2;
            }
        }
    }
    cout << answer;

    return 0;
}


Measured memory_bytes: 5220
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math

import itertools
import heapq
#import bisect

import copy
from functools import lru_cache

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)


def main():
    k=int(input())
    keta1=[x for x in range(1,10)]
    oriketa=copy.deepcopy(keta1)
    def next(keta,newketa):
        for i in range(len(keta)):
            plus=keta[i]%10+1
            eq=keta[i]%10
            minus=keta[i]%10-1
            if plus<=9:
                newketa.append(keta[i]*10+plus)
            newketa.append(keta[i]*10+eq)
            if minus>=0:
                newketa.append(keta[i]*10+minus)
        return
    ketan=[[] for i in range(10)]
    next(keta1,ketan[0])
    ketan[0]=sorted(ketan[0])
    oriketa.extend(ketan[0])
    for i in range(9):
        next(ketan[i],ketan[i+1])
        ketan[i+1] = sorted(ketan[i+1])
        oriketa.extend(ketan[i+1])

    #print(oriketa)
    print(oriketa[k-1])



if __name__ == "__main__":

    main()

Measured memory_bytes: 72560
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>
#include <iterator>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H,W,D;
  cin>>H>>W>>D;
  vector<pair<int,int>> A(H*W);
  REP(i,H*W){
    int a;
    cin>>a;
    a--;
    A[a]=make_pair(i-i/W*W,i/W);
  }

  vector<vector<int>> sum(D);
  REP(i,D){
    sum[i].push_back(0);
    int now=i;
    while(now+D<H*W){
      int last=sum[i].back();
      int diff=abs(A[now+D].first-A[now].first)+abs(A[now+D].second-A[now].second);
      sum[i].push_back(last+diff);
      now+=D;
    }
  }

  int Q;
  cin>>Q;
  REP(i,Q){
    int l,r;
    cin>>l>>r;
    l--;r--;
    int mo=l%D;
    cout<<sum[mo][r/D]-sum[mo][l/D]<<endl;
  }
}


Measured memory_bytes: 6144