akhauriyash/Code-Regression huggingface dataset:
import Data.List

main = readLn >>= print.solve

solve n =
    let xs = map length$group$factorize p100$product [1..n]
        [a,b,c,d,e] = map (over xs) [2,4,14,24,74]
    in div (b * (b-1)) 2 * (a-2) + c * (b-1) + d * (a-1) + e

over xs n = length(filter(>=n)xs)

p100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

factorize [] _ = []
factorize pr@(p:ps) n = if n`rem`p==0 then p:(factorize pr (n`quot`p)) else factorize ps n

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
int main()
{ int n,m;int w=0;int c=0;
   cin>>n>>m;
   int p[m];

   string s,s1="WA",s2="AC";int a[n+1]={0},b[n+1]={0};
   for(int i=0;i<m;i++)
     {
       cin>>p[i];
       cin>>s;
       if(s==s2)
       {
            a[p[i]]=1;
       }
      else if(s==s1)
       {
           if(a[p[i]]!=1)
           {
               b[p[i]]++;
           }
       }
     }
     for(int i=1;i<=n;i++)
     {   if(a[i]==1)
            {

            c++;
             w+=b[i];}
     }
     cout<<c<<" "<<w;


}


Measured memory_bytes: 1408
import math


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


main()


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, ans = 0, maxi = 0;;
	cin >> n;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		if(x >= maxi){
			maxi = x;
			ans ++;
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
let () = 
	let make_row n =
		let buf = Buffer.create n in
		for i = 1 to n + 1 do 
			Buffer.add_char buf (if i mod 2 = 1 then '#' else '.');
		done;
		let str = Buffer.contents buf in
		(Str.string_before str n, Str.string_after str 1) in
		
    let rec f _ = 
        let (h, w) = Scanf.sscanf(read_line()) "%d %d" (fun x y -> (x, y)) in
        if h = 0 && w = 0 then ()
        else (
            let (odd_row, even_row) = make_row w in
            for i = 1 to h do
            	Printf.printf "%s\n" (if i mod 2 = 1 then odd_row else even_row);
            done;
            print_newline ();
            f ()
        )
        
    in f ();;


Measured memory_bytes: 2288
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
#define endl '\n';
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;


int main() {
    int n,m;
    cin>>n>>m;
    vi v(n,0);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        v[a-1]++;
        v[b-1]++;
    }
    bool ch=1;
    rep(i,n)if(v[i]%2!=0)ch=0;
    YN(ch);
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=0;i<b;i++)
#define REP(i,a,b) for(int i=0;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout <<(f?"Yes":"No")<<endl//fが真の場合Yesを出力、偽の場合Noを出力
#define yes(f) cout <<(f?"yes":"no")<<endl
#define YES(f) cout <<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())

using namespace std;

const int mod=1e9+7;

signed main(){
    int n,x;
    cin >> n >> x;
    int l,ans=0;
    int now=0;
    rep(i,n+1)
    {
    cin >> l;
        if(now<=x)ans++;
        else
            break;
        now+=l;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
package main

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

func main() {

	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	sc.Text()

	list := list()

	for {
		sc.Scan()
		in := sc.Text()
		if len(in) == 0 {
			break
		}
		ins := strings.Split(in, " ")
		command := ins[0]

		switch command {
		case "insert":
			num, _ := strconv.Atoi(ins[1])
			list.insert(num)
		case "delete":
			num, _ := strconv.Atoi(ins[1])
			list.delete(num)
		case "deleteFirst":
			list.deleteFirst()
		case "deleteLast":
			list.deleteLast()
		}
	}
	printLine(&list)

}

func printLine(list *DoublyLinkedList) {
	r := []string{}
	elem := list.top
	for {

		if !elem.first && !elem.last {
			r = append(r, strconv.Itoa(elem.val))
		}

		elem = elem.next
		if list.top == elem {
			break
		}
	}

	fmt.Println(strings.Join(r, " "))
}

type DoublyLinkedList struct {
	top *Element
}

type Element struct {
	prev  *Element
	next  *Element
	val   int
	first bool
	last  bool
}

func list() DoublyLinkedList {
	first := Element{nil, nil, 0, true, false}
	last := Element{nil, nil, 0, false, true}

	first.next = &last
	first.prev = &last
	last.next = &first
	last.prev = &first
	return DoublyLinkedList{&first}
}

func (list *DoublyLinkedList) insert(x int) {
	e := Element{list.top, list.top.next, x, false, false}
	list.top.next.prev = &e
	list.top.next = &e
}

func (list *DoublyLinkedList) delete(x int) {
	now := list.top
	for {
		if !now.first && !now.last && now.val == x {
			now.next.prev = now.prev
			now.prev.next = now.next
			return
		}
		now = now.next
		if now == list.top {
			return
		}
	}
}

func (list *DoublyLinkedList) deleteFirst() {
	target := list.top.next
	target.next.prev = target.prev
	target.prev.next = target.next
}

func (list *DoublyLinkedList) deleteLast() {
	target := list.top.prev.prev
	target.next.prev = target.prev
	target.prev.next = target.next
}



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

using namespace std;

#define eb emplace_back
#define ii pair<int, int>
#define OK (cerr << "OK" << endl)
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define all(x) x.begin(), x.end()
#define vvi vector<vector<int>>
#define vvii vector<vector<pair<int, int>>>
#define Mat(n, m, v) vector<vector<int>>(n, vector<int>(m, v))
#define endl '\n'

constexpr int INF = 2e18;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 3;

int f(int a, int b, int c) {
  if (a != b && b != c)
    return (a + b > c);
  return false;
}

// #define MULTIPLE_TEST_CASES
void solve() {
  int n;
  cin >> n;

  vector<int> arr(n);
  int ans = 0;
  for (int &x : arr) {
    cin >> x;
  }
  sort(all(arr));

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        // if (f(arr[i], arr[j], arr[k])) {
        //   debug(arr[i]);
        //   debug(arr[j]);
        //   debug(arr[k]);
        //   cerr << endl;
        // }
        ans += f(arr[i], arr[j], arr[k]);
      }
    }
  }
  cout << ans << endl;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;
#ifdef MULTIPLE_TEST_CASES
  cin >> t;
#endif
  while (t--)
    solve();
}

Measured memory_bytes: 3656
#include <stdio.h>

int main() {
    
    char s[12];
    int i = 0;
    scanf("%s", s);
    
    for (i = 0; i < 4; i++) {
        printf("%c", s[i]);
    }
    printf(" ");
    for (i = 4; i < 12; i++) {
        printf("%c", s[i]);
    }
    printf("\n");
    return 0;
}

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

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef long double ld;

const ll mod = (ll)1e9 + 7;
const ll mxN = 200200;



void solve(){
	ll n;cin>>n;
	vector<ld> A(n);
	ld t,a;cin>>t>>a;
	for(int i=0;i<n;i++){
		cin>>A[i];
		A[i]=t-0.006*A[i];
		A[i]=abs(A[i]-a);
	}
	cout<<min_element(all(A))-A.begin()+1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(20);
	cout << fixed;

	//ll t;cin>>t;while(t--)
	solve();

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long int mod = 1000000007;
long long gcd(long long a, long long b) {
	if (a < b) return gcd(b, a);
	long long r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
int main() {
	long long a;
	cin >>a;
	long long ans=0;
	for (size_t i = 1; i <= a; i++)
	{
		for (size_t j = 1; j <= a; j++)
		{
			for (size_t k = 1; k <= a; k++)
			{
				ans += gcd(gcd(i, j), k);
			}
		}
	}
	cout << ans;
}

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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

template<class T> using v = std::vector<T>;
template<class T> using vv = v<v<T>>;

const int mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
//const int mod = 998244353;

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;}


template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; }}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; }}

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;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
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];
    }
};

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

    int n; cin >> n;
    v<int> a(n), b(n), c(n-1);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n-1) cin >> c[i];


    int ans = 0;
    rep(i,n) {
        ans += b[a[i] - 1];
        if (a[i] - 1 == a[i-1] && i) ans += c[a[i] - 2];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
ls = [[x for x in input() + '#'] for i in range(n)] + [['#']*(m+1)]
yokodp = [[0 for x in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    yoko = 0
    for j in range(m+1):
        if ls[i][j] == '#':
            yokodp[i][j] = yoko
            yoko = 0
        else:
            yoko += 1
for i in range(n,-1,-1):
    check = 0
    for j in range(m,-1,-1):
        if yokodp[i][j] != 0:
            check = yokodp[i][j]
        if ls[i][j] == '.':
            yokodp[i][j] = check
tatedp = [[0 for x in range(m+1)] for i in range(n+1)]            
for j in range(m+1):
    tate = 0
    for i in range(n+1):
        if ls[i][j] == '#':
            tatedp[i][j] = tate
            tate = 0
        else:
            tate += 1
for j in range(m,-1,-1):
    for i in range(n,-1,-1):
        if tatedp[i][j] != 0:
            check = tatedp[i][j]
        if ls[i][j] == '.':
            tatedp[i][j] = check
ans = 0
for i in range(n):
    for j in range(m):
        if ls[i][j] == '.':
            ans = max(ans,tatedp[i][j] + yokodp[i][j] - 1)
import time
print(ans)


Measured memory_bytes: 248072
#include <bits/stdc++.h>
using namespace std;
string s,ans="";

int main() {
  cin >>s;
  for (int i=0;i<s.size();i++) {
    if (ans=="" && s.at(i)=='B') continue;
    else if (s.at(i)=='B') ans.erase(ans.size()-1,1);
    else ans+=s.at(i);
  }
  cout << ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long N,a,b;
  cin>>N>>a>>b;
  long long ans=0;
  if(N%(a+b)<=a){
    ans=(N/(a+b))*a+N%(a+b);
  }
  else{
    ans=(N/(a+b))*a+a;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
/*
START BY THE NAME OF ALMIGHTY ALLAH
THIS WONT BE ACCEPTED
STOP_GIVING_UP

██╗███████╗████████╗██╗ █████╗ ██╗  ██╗
██║██╔════╝╚══██╔══╝██║██╔══██╗██║ ██╔╝
██║███████╗   ██║   ██║███████║█████╔╝
██║╚════██║   ██║   ██║██╔══██║██╔═██╗
██║███████║   ██║   ██║██║  ██║██║  ██╗
╚═╝╚══════╝   ╚═╝   ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝




*/
#include<bits/stdc++.h>
#define l(i,a,n)for(int i=a;i<n;i++)
#define pb push_back
#define in insert
#define mp make_pair
#define lw(v) sort(v.begin(),v.end());
#define hi(v) sort(v.begin(),v.end(),greater<long long>());
#define all(v) v.begin(),v.end()
#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long t,r=1,r1=0,r2=0,k=0,a,b,c=1,m,d=0,n,e,f=0,x=0,g,p=0,q=0,y=0,z=0;
double kk=0;
    vector<pair<long long,long long>>v;
    vector<long long>u;
    map<string,long long>s;
    std::vector<int>::iterator it;
    string  s1,s2,s3,s4,s5,s6;
   cin>>s1;
   if(s1=="Sunny")
   {
       cout<<"Cloudy";
   }
 else if(s1=="Cloudy")
 {
     cout<<"Rainy";
 }
 else{

    cout<<"Sunny";
 }



}


Measured memory_bytes: 3544
#include<iostream>
#include<vector>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<vector<bool> > m;
ll ans;
ll w, h;
P s, g;
void dfs(P p, ll n) {
	if(n == 10) return;
	ll det = false;
	REP(i, 4) {
		if(det) break;
		ll nh = p.first + dx[i];
		ll nw = p.second + dy[i];
		ll cnt = 0;
		while(nh >= 0 && nh < h && nw >= 0 && nw < w) {
			if(P(nh, nw) == g) {
				ans = min(ans, n + 1);
				det = true;
				break;
			}
			if(m[nh][nw]) {
				if(cnt > 0) {
					m[nh][nw] = false;
					dfs(P(nh - dx[i], nw - dy[i]), n + 1);
					m[nh][nw] = true;
				}
				break;
			} else {
				nh += dx[i];
				nw += dy[i];
				++cnt;
			}
		}
	}
}

int main(void) {
	while(true) {
		cin>>w>>h;
		if(w == 0 && h == 0) break;
		m.resize(h);
		REP(i, h) m[i].resize(w);
		REP(i, h) {
			REP(j, w) {
				int x;
				cin>>x;
				if(x == 0) m[i][j] = false;
				else if(x == 1) m[i][j] = true;
				else if(x == 2) {
					s.first = i;
					s.second = j;
					m[i][j] = false;
				}
				else if(x == 3) {
					g.first = i;
					g.second = j;
					m[i][j] = false;
				}
			}
		}
		ans = INF;
		dfs(s, 0);
		if(ans != INF) cout<<ans<<endl;
		else cout<<-1<<endl;
	}
}

Measured memory_bytes: 2976
fun main(args: Array<String>) {
    val (N, K) = readLine()!!.split(" ").map{it.toLong()}
    val ps = Array(N.toInt()) {
        val (a, b) = readLine()!!.split(" ").map{it.toLong()}
        Pair(a, b)
    }
    ps.sortBy { it.first }

    var s = 0L

    for (p in ps) {
        s += p.second
        if (s >= K) {
            println(p.first)
            return
        }
    }
}

Measured memory_bytes: 82984
package main

import "fmt"

func main() {

	var (
		num, shuffle_num              int
		deck, shuffled_deck, new_deck string
	)

	for {

		fmt.Scanln(&deck)

		if deck == "-" {
			break
		}

		fmt.Scanln(&num)

		new_deck = deck

		for i := 0; i < num; i++ {
			fmt.Scanln(&shuffle_num)
			shuffled_deck = new_deck[shuffle_num:] + new_deck[:shuffle_num]
			new_deck = shuffled_deck
		}

		fmt.Println(new_deck)

	}
}



Measured memory_bytes: 1140
#include <stdio.h>
#include <string.h>

int main(void) {
	char s[11] = { 0 };
	int len;

	scanf("%s", &s);
	len = strlen(s);

	if (len >= 4) {
		if ((s[0] == 'Y') && (s[1] == 'A') && (s[2] == 'K') && (s[3] == 'I')) {
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#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>;

int main()
{
    int n;
    cin >> n;
    cout << ((2000 - n) + 200 - 1) / 200 << endl;
    return 0;
}

Measured memory_bytes: 3632
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)

bi_comb = []
for i in range(min(X, K)):
    for j in range(min(Y, K)):
        if (i+1)*(j+1) <= K:
            bi_comb += [A[i]+B[j]]
bi_comb.sort(reverse = True)

tri_comb = []
for k in range(min(len(bi_comb), K)):
    for l in range(min(Z, K)):
        if (k+1)*(l+1) <= K:
            tri_comb += [bi_comb[k]+C[l]]
tri_comb.sort(reverse = True)

print (*tri_comb[:K], sep='\n')


Measured memory_bytes: 44636
package main

import (
	"fmt"
	"sort"
)

const intMax = 2147483647

type MyInt int

// 構造体のスライス
type MyInts []MyInt

// 以下インタフェースを満たす

func (i MyInts) Len() int {
	return len(i)
}

func (i MyInts) Swap(a, b int) {
	i[a], i[b] = i[b], i[a]
}

func (i MyInts) Less(a, b int) bool {
	return i[a] < i[b]
}

func main() {
	var n, k int
	_, _ = fmt.Scan(&n)
	_, _ = fmt.Scan(&k)
	hs := make(MyInts, n)
	for i, _ := range hs {
		var h MyInt
		_, _ = fmt.Scan(&h)
		hs[i] = h
	}

	sort.Sort(sort.Reverse(hs))

	res := 0
	for i := k; i < n; i++ {
		res += int(hs[i])
	}
	fmt.Println(res)
}


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

int main() {
    string S, T;
    cin >> S >> T;
    int k=100;
    if (S.length()<T.length()) printf("%s\n", "UNRESTORABLE");
    else {
        for (int i=0; i<=S.length()-T.length();i++){
            for (int j=0; j<T.length();j++){
                if (S[i+j]!='?' && S[i+j]!=T[j]) {
                    break;
                }
                else if (j==T.length()-1 && (S[i+j]=='?' || S[i+j]==T[j])) k=i;
            }
        }
        if (k==100) printf("%s\n", "UNRESTORABLE");
        else {
            for (int i=0; i<S.length();i++){
                if (i<k&&S[i]=='?') S[i]='a';
                else if (k<=i &&i<k+T.length()) S[i]=T[i-k];
                else if (S[i]=='?') S[i]='a';
            }
            cout << S << endl;
        }
    }
}


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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

bool check[401][401] = { };

int main(){
	int n, q;
	cin >> n >> q;
	int a[n];
	REP(i, n) cin >> a[i];
	vector<ll> minturn(n);
	REP(i, n) minturn[i] = 0;
	REP(i, n-1){
		if(i >= (n-1-i)) minturn[i+1] = 1 + (a[i] + a[i - (n-1-i)])/2;
	}
	ll ans[n] = { };
	FOR(i, n/2, n) ans[0] += a[i];
	REP(i, n/2+1) ans[i] = ans[0];
	FOR(i, n/2+1, n){
		if(n%2 == 0) ans[i] = ans[i-1] - a[i-1] + a[2*(i-1-(n/2))+1];
		else ans[i] = ans[i-1] - a[i-1] + a[2*(i-1-(n/2))];
	}
	REP(xr, q){
		int x;
		cin >> x;
		int l = 0, r = n+1;
		while((r-l)!=1){
			int m = (l+r)/2;
			if(minturn[m] > x) r = m;
			else l = m;
		}
		if(l == n) cout << ans[n-1] << endl;
		else cout << ans[l] << endl;
	}
} 

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


using namespace std;
#define PI acos(-1)
using P =pair<ll,ll>;

ll ketasu(ll a){
   ll num=1;
   while(a/10){
       num++;
       a/=10;
   }
   return num;
}

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

ll kosuu(ll a){
    ll sum=0;
    for(ll i=1;i*i<=a;i++){
        if(a%i==0){
            if(a!=1&&i*i!=a){
            sum+=2;
            }else{
             sum++;   
            }
        }
    }
    return sum;
}

ll n;



    vector<pair<ll,ll>>p;
void fs(ll a){
    for(ll i=2;i*i<=n;i++){
        ll cnt=0;
        while(n%i==0){
            n/=i;
            cnt++;
        }
        p.emplace_back(i,cnt);
    }
    return;
}


ll di[]={1,0,-1,0};
ll dj[]={0,-1,0,1};
int main(){
   int n;
   cin>>n;
    long long int a[n],ans=0,i;
    int mod=1000000007;
    long long int sum=0;
 
    for( i = 0 ; i < n ; i++ ){
            cin>>a[i];
    }
    rep(i,n)sum+=a[i];
    for( i = 0 ; i < n ; i++ ){
        sum = sum - a[i];
 
        ans+=(sum%mod * a[i]%mod)%mod;
    }
    cout<<ans%mod;
 
    return 0;
}
 




Measured memory_bytes: 5160
/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 1/12/2019, 9:15:17 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
const ll infty = 100000000007;

int N, Q;
ll A[100010];
vector<ll> B;
ll X[100010];
set<ll> S;
map<ll, ll> M;
ll Y[100010];
ll Z[100010];

void flush()
{
  for (auto i = 0; i < Q; i++)
  {
    cout << M[X[i]] << endl;
  }
}

int main()
{
  cin >> N >> Q;
  for (auto i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  for (auto i = 0; i < Q; i++)
  {
    cin >> X[i];
    S.insert(X[i]);
  }
  reverse(A, A + N);
  Y[N + 1] = 0;
  Y[N] = 0;
  Y[N - 1] = A[N - 1];
  Y[N - 2] = A[N - 2];
  for (auto i = N - 3; i >= 0; i--)
  {
    Y[i] = A[i] + Y[i + 2];
  }
  Z[0] = A[0];
  for (auto i = 1; i < N; i++)
  {
    Z[i] = A[i] + Z[i - 1];
  }
  B.push_back(infty);
  for (auto i = 0; i < N; i++)
  {
    B.push_back(A[i]);
  }
  B.push_back(-infty);
  auto it = S.begin();
  for (auto i = N; i >= 0; i--)
  {
    int second = i / 2;
    int first = i - second;
    ll score;
    if (first == 0)
    {
      score = Y[0];
    }
    else if (first == second)
    {
      score = Z[first - 1] + Y[i];
    }
    else
    {
      score = Z[first - 1] + Y[i + 1];
    }
    ll upper, lower;
    if (second == 0)
    {
      upper = infty;
      lower = -infty;
    }
    else
    {
      ll FA = B[first];
      ll FB = B[first + second];
      upper = (FA + FB) / 2;
      ll GA = B[first + 1];
      ll GB = B[first + second + 1];
      lower = (GA + GB) / 2 + 1;
    }
    // cerr << "i = " << i << ", upper = " << upper << ", lower = " << lower << endl;
    while (it != S.end())
    {
      if (lower <= *it && *it <= upper)
      {
        M[*it] = score;
        it++;
      }
      else
      {
        break;
      }
    }
  }
  assert(it == S.end());
  flush();
}

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

int main(){
  ll k;cin >> k;
  rep(i,k) cout << "ACL";
  cout << endl;

  return 0;
} 

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int max=0;
	int n2;
	for(int i=1;i<=n;i++)
	{
		int p=i;
		int count=0;
		while(p%2==0)
		{
			p=p/2;
			count++;	
		}
		if(max<count)
		{
			n2=i;
			max=count;
		}
	}
	if(n==1)
		n2=1;
	if(n==2)
		n2=2;
	cout<<n2;
}

Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int i,j,h,w;
	while(1)	{
		scanf("%d %d",&h,&w);
		if(h==0 && w==0)	break;
		for(i=0;i<h;i++)	{
			for(j=0;j<w;j++)	{
				if((i+j)%2==0)	{
					printf("#");
				}
				else {
					printf(".");
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}


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

#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
string backst(int cnt) {
	string s;
	while (cnt) {
		s += to_string(cnt % 10);
		cnt /= 10;
	}
	return s;
}
string fizzbuzz(int x) {
	if (x % 15 == 0)return "FizzBuzz";
	else if (x % 5 == 0)return "Buzz";
	else if (x % 3 == 0)return "Fizz";
	else {
		ostringstream os;
		os << x;
		return os.str();
	}
}
signed main() {
	int m, n;
	while (cin >> m >> n, m || n) {
		vector<bool>v(m, true);// v[0] = false;
		int cnt(1), index(0);
		string s;
		while (n--) {
			cin >> s;
			if (v.size() == 1)continue;
			if (accumulate(all(v), 0) == 1)continue;
			while (v[index%m] == false)index++;

			if (fizzbuzz(cnt) != s)v[index%m] = false;

			cnt++; index++;
		}
		bool f(true);
		rep(i, 0, m) {
			if (v[i]) {
				if (f)f = false;
				else cout << " ";
				cout << i + 1 ;
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3192
S = int(input())

num_list = [S]

while True:
    if S % 2 == 0:
        S = int(S / 2)
    else:
        S = int(S * 3 + 1)

    if S in num_list:
        break;  
    num_list.append(S)

print(len(num_list)+1)

Measured memory_bytes: 2940
#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(obj) (obj).begin(),(obj).end()

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,a,b;cin>>n>>a>>b;
  vector<int> x(n);
  rep(i,n)cin>>x[i];
  ll tot=0;
  rep(i,n-1){
      if(a*(x[i+1]-x[i])>b)tot+=b;
      else tot+=a*(x[i+1]-x[i]);
  }
  cout<<tot<<endl;
  return 0;
  }


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
#define ll long long
#define MOD 1000000007

int main() {
	ll N, K = 0;
	cin >> N;
	for (ll i = 1;i <= N;i++) {
		if (i % 3 == 0)continue;
		if (i % 5 == 0)continue;
		K += i;
	}
	cout << K << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cmath>
#include <string>
#include <map>
#include <queue>
using namespace std;
#define N 3

struct Puzzle {
  int f[N*N];
  int space;
  string path;

  bool operator < ( const Puzzle &p ) const {
    for(int i=0;i < N*N; i++){
      if(f[i]==p.f[i]) continue;
      return f[i]>p.f[i];
    }
    return false;
  }
};

static const int dx[4]={-1,0,1,0};
static const int dy[4]={0,-1,0,1};
static const char dir[4]={'u','l','d','r'};

bool isTarget(Puzzle p){
  for(int i=0;i<N*N;i++)
    if(p.f[i]!=(i+1)) return false;
  return true;
}

string bfs(Puzzle s){
  queue<Puzzle> Q;
  map<Puzzle,bool> V;
  Puzzle u,v;
  s.path="";
  Q.push(s);
  V[s]=true;

  while(!Q.empty()){
    u=Q.front(); Q.pop();
    if(isTarget(u)) return u.path;
    int sx=u.space/N;
    int sy=u.space%N;
    for(int r=0;r<4;r++){
      int tx=sx+dx[r];
      int ty=sy+dy[r];
      if(tx<0||ty<0||tx>=N||ty>=N) continue;
      v=u;
      swap(v.f[u.space],v.f[tx*N+ty]);
      v.space=tx*N+ty;
      if(!V[v]){
	V[v]=true;
	v.path+=dir[r];
	Q.push(v);
      }
    }
  }
  return "unsolvable";
}

int main()
{
  Puzzle in;

  for(int i=0;i<N*N;i++){
    cin>>in.f[i];
    if(in.f[i]==0){
      in.f[i]=N*N;
      in.space=i;
    }
  }
  string ans=bfs(in);
  cout<<ans.size()<<endl;

  return 0;
}

Measured memory_bytes: 30476
#include <bits/stdc++.h>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	int x[n],X[n];
    	for(int i=0;i<n;i++){
    		cin>>x[i];
    		X[i]=x[i];
    	}
    	sort(X,X+n);
    	int a=X[n/2-1],b=X[n/2];
    	for(int i=0;i<n;i++){
    		if(x[i]<b) cout<<b<<endl;
    		else cout<<a<<endl;
    	}
    	return 0;
    }

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

int main(){
    int a, b, ab, ab_sq;
    string ab_str;

    cin >> a >> b;
    ab_str = to_string(a) + to_string(b);
    ab = stoi(ab_str);
    ab_sq = (int) sqrt(ab);

    if (ab_sq * ab_sq == ab) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;

}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    while (cin >> n, n)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            int m = i;
            while (m % 5 == 0)
            {
                cnt++;
                m /= 5;
            }
        }
        OP(cnt);
    }
    return 0;
}


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

typedef struct {
    double y, x;
} p_t;

int main() {   
    Int n;
    cin >> n;
    vector<pair<Int, Int>> v(n);
    for (Int i = 0; i < n; i++) {
        Int a, b;
        cin >> a >> b;
        v[i].se = a - b + 1;
        v[i].fi = a + b;
    }
    sort(all(v));
    for (Int i = 0; i < n; i++) {
        swap(v[i].fi, v[i].se);
    }
    Int time = -INF;
    Int cnt = 0;
    for (Int i = 0; i < n; i++) {
        if (time < v[i].fi) {
            cnt++;
            time = v[i].se;
        }
    }
    dump(cnt);
    return 0;
}


Measured memory_bytes: 1792
#include<cstdio>
#include<cstring>
#define ll long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
ll a[100500];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	ll ans=1e10;
	for (int l=1;l+k-1<=n;l++){
		int r=l+k-1;
		if (a[r]>=0&&a[l]<=0) {
			if (min(a[r],-a[l])*2+max(a[r],-a[l])<ans) 
				ans=min(a[r],-a[l])*2+max(a[r],-a[l]);
		}
	}
	int x=k;
	for (int i=1;i<=n;i++){
		if (a[i]>=0) x--;
		if (x==0) ans=min(ans,a[i]);
	}
	x=k;
	for (int i=n;i>0;i--){
		if (a[i]<=0) x--;
		if (x==0) ans=min(ans,-a[i]);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 896
package main

import (
	"fmt"
	"math"
)

func main() {
	var x int
	fmt.Scan(&x)

	m := 100
	for i := 0; ; i++ {
		if m >= x {
			fmt.Println(i)
			return
		}
		m = int(math.Trunc(float64(m) * 1.01))
	}
}


Measured memory_bytes: 1756
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;

typedef long long ll;

#define MAX_V 100
#define INF int(1e9)

struct Edge {
    int v, cost;
    Edge() {}
    Edge(int v, int cost) : v(v), cost(cost) {}
};

// g[] : ????????????????????°???????????£??\?????????, V : ????????°, s : ?§??????¨????????????, d[] : s????????????????????????????´?????????????
int Dijkstra (vector<Edge> g[], int V, int s, int d[]) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(make_pair(0, s)); // pair(cost, vertex)

    while (!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();
        int v = p.second, size_ = g[v].size();

        if (d[v] < p.first) continue;

        for (int i = 0; i < size_; ++i) {
            Edge e = g[v][i];
            if (d[e.v] > d[v] + e.cost) {
                d[e.v] = d[v] + e.cost;
                que.push(make_pair(d[e.v], e.v));
            }
        }
    }

}

int n, u, k, v, c, d[MAX_V + 1];
vector<Edge> g[MAX_V + 1]; // ????????°??????

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

    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            cin >> v >> c;
            g[u].push_back(Edge(v, c));
        }
    }

    Dijkstra(g, n, 0, d);

    for (int i = 0; i < n; ++i) {
        cout << i << " " << d[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
int main(){
  	ll n;
  	cin >> n; 
  	ll t=sqrt(n);
	ll ans=1e12;
	for(ll i=1; i<=t; i++){
  		ll tp = n/i;
  		if(tp*i == n){
  			ans = min(tp-1+i-1, ans);
  			//cout << i << " " <<tp << " " <<ans << endl;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
  vector<vector<char>> input(2, vector<char>(3));
  vector<vector<char>> vec1(2, vector<char>(3));
  vector<vector<char>> vec2(2, vector<char>(3));
  for(int i = 0; i < 2; i++)
  {
    for(int j = 0; j < 3; j++)
    {
      cin >> input.at(i).at(j);
    }
  }
  copy(input.at(0).begin(), input.at(0).end(), vec2.at(0).begin());
  copy(input.at(1).begin(), input.at(1).end(), vec2.at(1).begin());
  
  reverse(input.at(0).begin(), input.at(0).end());
  reverse(input.at(1).begin(), input.at(1).end());
  
  copy(input.at(1).begin(), input.at(1).end(), vec1.at(0).begin());
  copy(input.at(0).begin(), input.at(0).end(), vec1.at(1).begin());

  
  if(vec1== vec2)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}

Measured memory_bytes: 256
//we'll get thru it believe me 
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
void mod(int& a){
	if(a>=MOD)a-=MOD;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int R, C;
	cin>>R>>C;
	vector<vector<int>>dp(R, vector<int>(C, 0));
	vector<string>A(R);
	for(auto&a:A)cin>>a;
	dp[0][0]=1;
	for(int r=0; r<R; r++){
		for(int c=0; c<C; c++){
			if(A[r][c]=='#')continue;
			if(r<R-1&&A[r+1][c]!='#'){
				dp[r+1][c]+=dp[r][c];
				mod(dp[r+1][c]);
			}
			if(c<C-1&&A[r][c+1]!='#'){
				dp[r][c+1]+=dp[r][c];
				mod(dp[r][c+1]);
			}
		}
	}
	cout<<dp[R-1][C-1];
}


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

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

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


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def solve():
    n = getN()
    nums = getList()
    d = dict()
    for num in nums:
        res = primeFactor(num)
        for k, v in res.items():
            if k not in d:
                d[k] = v
            elif d[k] < v:
                d[k] = v


    big = 1
    for k, v in d.items():
        big *= pow(k, v, MOD)
        big %= MOD
    ans = 0
    for num in nums:
        ans += big * divide(num)
        ans %= MOD

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

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







Measured memory_bytes: 76208
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main(){
	lli n,k;
	cin>>n>>k;
	lli arr[n];
	for(lli i=0;i<n;i++) cin>>arr[i];
	vector<lli>dp(n,INT_MAX);
	dp[0]=0;dp[1]=abs(arr[0]-arr[1]);
	for(lli i=2;i<n;i++){
		for(lli j=1;j<=min(i,k);j++)
			dp[i]=min(dp[i-j]+abs(arr[i]-arr[i-j]),dp[i]);
	}
	cout<<dp[n-1];
}

Measured memory_bytes: 4836
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};//RBLF
int n,m,cnt;
vs in;
vvi num;
void dfs(int a,int b,char c){
	in[a][b]='!';
	num[a][b]=cnt;
	rep(i,8){
		if(c=='.'&&i==4)break;
		int x=a+dx[i];
		int y=b+dy[i];
		if(x<0||x>=n+2||y<0||y>=m+2)continue;
		if(in[x][y]!=c)continue;
		dfs(x,y,c);
	}
}
vvi f(){
	cin>>n>>m;
	if(!n)return vvi(0);
	in=vs(n+2,string(m+2,'.'));
	num=vvi(n+2,vi(m+2));
	vvi G(1);
	rep(i,n){
		string s;cin>>s;
		in[i+1]="."+s+".";
	}
	cnt=0;
	
	rep(i,n+2)rep(j,m+2)if(in[i][j]!='!'){
		if(cnt){
			G[num[i][j-1]].pb(cnt);
			G.pb(vi(0));
		}
		dfs(i,j,in[i][j]);
		cnt++;
	}
	return G;
}
vvi G;
vi Rand(100000);
ll MOD=1000000009;
ll Hash(int a,int b){
	vi in;
	ll out=1;
	rep(i,G[a].size())(out*=(Rand[b]+Hash(G[a][i],b+1))%MOD)%=MOD;
	return out;
}
int main(){
	random_device rnd;
	rep(i,100000)Rand[i]=rnd()%MOD;
	while(1){
		G=f();
		if(G.size()==0)break;
		ll A=Hash(0,0);
		G=f();
		ll B=Hash(0,0);
//		cout<<A<<" "<<B<<endl;
		if(A==B)cout<<"yes"<<endl;
		else cout<<"no"<<endl;
	}
}












Measured memory_bytes: 4016
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		Scanner scn = new Scanner(System.in);
		int a = scn.nextInt();
		int v = scn.nextInt();
      	int b = scn.nextInt();
      	int w = scn.nextInt();
      	int t = scn.nextInt();
      	double tt;
      	String ans = "YES";
      	if(b>a){
          tt = (double)(b-a)/(v-w);
          if(t<tt) ans = "NO";
          if(w>v) ans = "NO";
        }
      	if(a>b){
          tt = (double)(a-b)/(v-w);
          if(t<tt) ans = "NO";
          if(w>v) ans = "NO";
        }
      	System.out.println(ans);
	}
}


Measured memory_bytes: 35588
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define IOS cin.tie(0),ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty())return out;
    constexpr bool is_vector_v = is_vector<T>::value;
    if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
    else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
    return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector<vector<int>> a2(n,vector<int>(m));
    REP(i, n) {
        REP(j, m) {
            cin >> a2[i][j];
        }
    }
    REP(i,n){
        REP(j,m){
            a[i][a2[i][j]-1]=j+1;
        }
    }
    int res = INT_MAX;
    vector<int> ch(m, 1);
    REP(i, m) {
        vector<int> arg(n, -1);
        REP(j, m) {
            if (ch[j]) {
                REP(k, n) {
                    if (arg[k] == -1) {
                        arg[k] = j;
                    } else {
                        if (a[k][j] < a[k][arg[k]]) {
                            arg[k] = j;
                        }
                    }
                }
            }
        }
        vector<int> cnt(m, 0);
        REP(j, n) {
            cnt[arg[j]]++;
        }
        int index = max_element(all(cnt))-cnt.begin();
        chmin(res,*max_element(all(cnt)));
        ch[index] = 0;
    }
    put(res);
    return 0;
}


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

int main() {
int n,a;
  cin>>n;
  vector<int> vec(n);
  for(int i=0;i<n-1;i++){
  cin>>a;
  vec.at(a-1)++;
    
  }
  for(int i=0;i<n;i++){
  cout<<vec.at(i)<<endl;
  
  }
}

Measured memory_bytes: 4052
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set; 

int main(){
    fastio
    string s ; 
    cin >> s ;
   	vector<string> t = { "dream" , "dreamer" , "erase" , "eraser" } ;  
   	while((int)s.size()>=5){
   		int n = (int) s.size() ; 
   		debug() << imie(n) ;
   		if ( s.substr(n-5) == t[0] || s.substr(n-5) == t[2] ){
   			debug() << imie(s.substr(n-5));
   			s.erase(n-5) ; 
   			debug() << imie(s);
   			continue ; 
   		}
   		else if ( n >= 6 && s.substr(n-6) == t[3] ){
   			debug() << imie(s.substr(n-6));
   			s.erase(n-6) ; 
   			debug() << imie(s) ; 
   			continue ; 
   		}
   		else if ( n >= 7 && s.substr(n-7) == t[1]){
   			debug() << imie(s.substr(n-7));
   			s.erase(n-7) ; 
   			debug() << imie(s) ;
   			continue ; 
   		}
   		break;
   	}
   	if ( s.size() == 0 ){
   		cout << "YES" << endl;
   	}
   	else cout << "NO" << endl;
   	return 0 ;
   }



Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[100010];
int main(){
	cin>>n>>m;
	a[0]=1;
	for(long long i=0;i<m;i++){
		int x;
		cin>>x;
		a[x]=-1;
	}
	for(long long i=1;i<=n;i++){
		if(a[i]!=-1){
			if(a[i-1]!=-1)
				a[i]+=a[i-1]%1000000007;
			if(a[i-2]!=-1)
				a[i]+=a[i-2]%1000000007;
		}
	}
	cout<<a[n]%1000000007;
	return 0;
}

Measured memory_bytes: 1024