akhauriyash/Code-Regression huggingface dataset:
#A
"""
a,b = map(int, input().split())
if b % a == 0:
    print(b + a)
else:
    print(b-a)
"""

#B

n, m = map(int, input().split())
ans = list(map(int, input().split()))
del ans[0]
ans = set(ans)
for i in range(n-1):
    a = list(map(int, input().split()))
    del a[0]
    ans = ans & set(a)
print(len(ans))


#C
"""
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
print(gcd_list(a))
"""

Measured memory_bytes: 3064
n = raw_input()
ais = map(int, raw_input().split())
s = sum(ais)
cumul = 0
ans = 0
mod = (10 ** 9 + 7)
for i in range(len(ais)):
	cumul += ais[i]
	ans += ais[i] * (s - cumul)
	ans %= mod
print ans % mod


Measured memory_bytes: 94928
#include<functional>
#include<list>
#include<queue>
#include<stack>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


class word{
 public:
  char w[31];
  std::priority_queue<int> q;
};


int main(){
  using namespace std;  
  int p,cmp;
  char str[31];
  list<word> wlst;
  list<word>::iterator it;
  stack<int> b;
  word *buf;

  while(scanf("%s %d",str,&p)!=EOF){
    it=wlst.begin();
    while(it!=wlst.end()){
      cmp=strcmp(it->w,str);
      if(!cmp){
	it->q.push(p);
	break;
      }else if(cmp>0){
	buf=new word();
	strcpy(buf->w,str);
	buf->q.push(p);
	wlst.insert(it,*buf);
	break;
      }
      ++it;
    }
    if(it==wlst.end()){
      buf=new word();
      strcpy(buf->w,str);
      buf->q.push(p);
      wlst.insert(it,*buf);
    }
  }
  it=wlst.begin();
  while(it!=wlst.end()){
    printf("%s\n",it->w);
    while(!(it->q.empty())){
      b.push(it->q.top());
      it->q.pop();
    }
    while(1){
      printf("%d",b.top());
      b.pop();
      if(b.empty()){
	printf("\n");
	break;
      }else{
	printf(" ");
      }
    }
    it++;
  }
  return 0;
}

Measured memory_bytes: 0
// created_by  Rishi_Mohan

#include<bits/stdc++.h>

#define    ll           long long
#define    db1(x)       cout<<#x<<"="<<x<<'\n'
#define    db2(x,y)     cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define    db3(x,y,z)   cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'

using namespace std;

void solve()
{
  int k;
  cin >> k;
  string s;
  cin >> s;

  if(s.length()<=k) cout << s << endl;
  else
  {
    s.erase(s.begin()+k,s.end());
    s+="...";
    // while(k--)
    // {
    //     s+='.';
    // }
    cout << s << endl;
  }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}


Measured memory_bytes: 3552
import java.util.Scanner

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val h = scanner.nextInt()

    val a = Array<Int>(n, { 0 })
    val b = Array<Int>(n, { 0 })

    for (i in 0..(n - 1)) {
        a[i] = scanner.nextInt()
        b[i] = scanner.nextInt()
    }
    val aMax : Int = a.max()!!
    val b2 = b.sortedDescending().filter { it > aMax }
    val b2Length = b2.size

    var damage = 0
    for (i in 0..(b2Length - 1)) {
        damage += b2[i]
        if (damage >= h) {
            println(i + 1)
            return
        }
    }
    if ((h - damage) % aMax == 0) {
        println(b2Length + (h - damage) / aMax)
    } else {
        println(b2Length + (h - damage) / aMax + 1)
    }
}

Measured memory_bytes: 76272
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<string,ll>;



int main(){
	ll N;
	cin >> N;
	vector<ll> A(N+1,0);
	vector<ll> B(N+1,0);
	vector<ll> C(N,0);
	ll sum=0;
	for(ll i=0;i<N;i++){
		cin>>A[i+1]
	;}
	for(ll i=0;i<N;i++){
		cin>>B[i+1];
		sum+=B[i+1];
	;}
	for(ll i=0;i<N-1;i++){
		cin>>C[i+1]
	;}
	for(ll i=1;i<N;i++){
		if(A[i+1]==A[i]+1)sum+=C[A[i]]
	;}
	cout<<sum<<endl;
return 0;
}  



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if (A == B && B != C ||
      B == C && C != A ||
      C == A && A != B)
  {
    cout << "Yes" << endl;
  } 
  else
  {
    cout << "No" << endl;
  }
}

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

int main(){
  int a, b;
  string str_a = "";
  string str_b = "";
  
  cin >> a >> b;
  for(int i=0;i<a;i++){
    str_b += to_string(b);
  }
  for(int i=0;i<b;i++){
    str_a += to_string(a);
  }
  
  if(a<b)
    cout << str_a << endl;
  else
    cout << str_b << endl;
  
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long count = 0;

		for(int i=1; i<(n+1); i++){
			if(!(i%3==0||i%5==0)){
				count+=i;
			} 
		}
		System.out.println(count);
	    scan.close();	
    }
}

Measured memory_bytes: 35812
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            //            List<int> A = new List<int>();
            int[] A = new int[N];
            int[] A_result = new int[N];
            string[] A_in = Console.ReadLine().Split(' ');
            StringBuilder output = new StringBuilder();
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(A_in[i]);
                A_result[A[i] - 1] = i + 1;
            }
            for (int i = 0; i < N; i++)
            {
                output.Append(A_result[i].ToString() + " ");
            }

            Console.WriteLine(output.ToString());
//            Console.Read();
        }
    }
}

Measured memory_bytes: 30552
#include <iostream>
#include <queue>

using namespace std;

struct C {
    int n;
    C() {}
    C(int n) : n(n) {}
    int x() {
        return (n % 5 == 1 ? 5 : 2);
    }
    int time() {
        return 17 * (n % 2) + 3 * (n % 3) + 19;
    }
    int arrival() {
        return n * 5;
    }
};

#define INF (1000000)

int T[100];
int S[17];

bool isEmpty(int t, int x) { // is there x consecutive empty seat after t minutes later
    for (int i = 0; i < 17 - x + 1; i++) {
        bool xEmpty = true;
        for (int j = 0; j < x; j++) {
            if (S[i+j] > t) {
                xEmpty = false;
                break;
            }
        }
        if (xEmpty) {
            return true;
        }
    }
    return false;
}

void fillSeat(int t, C c) {
    int x = c.x();
    for (int i = 0; i < 17 - x + 1; i++) {
        bool xEmpty = true;
        for (int j = 0; j < x; j++) {
            if (S[i+j] > t) {
                xEmpty = false;
                break;
            }
        }
        if (xEmpty) {
            for (int j = 0; j < x; j++) {
                S[i+j] = t + c.time();
            }
            return;
        }
    }
    cerr << "Something wrong." << endl;
}

int seat(C c) {
    int lb = -1, ub = INF;
    while (lb + 1 != ub) {
        int mid = (lb + ub) / 2;
        if (isEmpty(mid, c.x())) {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    //cout << c.n << " " << ub << endl;
    //for (int i = 0; i < 17; i++) cout << S[i] << ' '; cout << endl;
    int t = max(c.arrival(), ub);
    fillSeat(t, c);
    return t;
}

void init() {
    queue<C> q;
    for (int i = 0; i < 100; i++) {
        q.push(C(i));
    }
    while (!q.empty()) {
        C c = q.front(); q.pop();
        T[c.n] = seat(c);
        if (c.x() == 5) {
            // dirty hack
            for (int i = 0; i < 17; i++) {
                S[i] = max(S[i], T[c.n]);
            }
        }
    }
}

int main() {
    int n;
    init();
    while (cin >> n) {
        cout << T[n] - C(n).arrival() << endl;
    }
    return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int x1, x2, y1, y2;
    cin >> y1 >> y2 >> x1 >> x2;
    int ans = 0;
    if (x1 != -1 && x2 != -1){
        if (x1 > x2) ans = 1;
        else if (x1 < x2) ans = -1;
    }else{
        if (y1 < y2) ans = 1;
        else if (y1 > y2) ans = -1;
    }
    cout << vector<string>({"Bob", "Draw", "Alice"})[ans + 1] << endl;
    return 0;
}



Measured memory_bytes: 3212
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;

using namespace std;

int main()
{
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b < c + d)
  {
    cout << "Right" << endl;
  }
  else if (a + b == c + d)
  {
    cout << "Balanced" << endl;
  }
  else
  {
    cout << "Left" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define PR printf
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef pair<pii,pii> ppp;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef map<int,int> mii;
const int INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
int inline nextin(){
	int t;
	if(scanf("%d",&t)!=1)exit(0);
	return t;
}
int inline in(){
	int x=0,c;
	for(;(uint)((c=getchar())-'0')>=10;){
		if(c=='-')return -in();
		if(!~c)throw ~0;
	}
	do{
		x=(x<<3)+(x<<1)+(c-'0');
	}while((uint)((c=getchar())-'0')<10);
	return x;
}
int main(){
    cin.sync_with_stdio(false);cin.tie(0);
	int k,x;
	cin>>k>>x;
	for(int i=x-k+1;i<=x;i++){
		if(i<-1000000)continue;
		cout<<i<<' ';
	}
	for(int i=x+1;i<x+k;i++){
		if(i>1000000)break;
		cout<<i<<' ';
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int ans = a;
		for(int i=2; a >= i; i=i*2) {
			ans = i;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 25684
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
ll mod=1e9+7;
int a[400];
pair<ll,ll> dp[400][400];
void f(int st, int end){
    if(st==end){
        dp[st][st]={0,a[st]};
        return ;
    }
    ll l=1e18;
    ll p;
    for(int i=st;i<=end-1;i++){
        if(dp[st][i].first==-1) f(st,i);
        if(dp[i+1][end].first==-1) f(i+1,end);
        ll c=dp[st][i].first+dp[i+1][end].first+dp[st][i].second+dp[i+1][end].second;
        if(c < l){
            l=c;
            p=dp[st][i].second+dp[i+1][end].second;
        }
    }
    dp[st][end]={l,p};
}
int main() {
/*
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
    #endif*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<400;i++){
        for(int j=0;j<400;j++){
            dp[i][j]={-1,-1};
        }
    }
    f(0,n-1);
    cout<<dp[0][n-1].first;
}

Measured memory_bytes: 2816
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

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

int main() {
  int n;
  cin>>n;
  
  vector<tuple<string,int,int>> vec(n);
  rep(i,n){
    string x;
    int y;
    cin>>x>>y;
    tuple<string,int,int> p;
    p=make_tuple(x,100-y,i+1);
    vec[i]=p;
  }
  
  sort(ALL(vec));
  
  rep(i,n) cout << get<2>(vec[i]) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <math.h>
// #include <cmath>
// #include <vector>
// #include <utility> 
// #include <unordered_map>
// #include <map>
// #include <string>

using namespace std;
typedef long long int lli;

#define M_PI_H  3.14159265358979323846/2  /* pi by two*/
#define rep(i, start, end) for(int i = start; i < end; i++) 
#define repr(i, start, end) for(int i = start; i >= end; i--)   //INCLUSIVE



int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
	
	int x, y; cin>>x>>y;

	int b = y-2*x;
	if(b<0) {cout<<"No"; return 0;}

	if(b%2==0){
		b/=2;
		if(b>x){
			cout<<"No";
		} else {
			cout<<"Yes";
		}
	} else {
		cout<<"No";
	}
    return 0;
}

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

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

    int ans = 0;
    for(int i = 0;i <4;i++){
        char a;
        cin >> a;
        if(a == '+'){
            ans++;
        }else{
            ans--;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    vector<P>V(N);
    rep(i,0,N){
        cin >> V[i].second >> V[i].first;
    }
    sort(V.begin(), V.end());
    ll sum = 0;
    rep(i,0,N){
        sum += V[i].second;
        if(sum > V[i].first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}




struct BIT{
  vector<int> bit;
  int n;

  BIT(int m){
    n = m;
    bit.assign(2*n,0);
  }

  int sum(int i){
    int s = 0;
    while(i>0){
      s+=bit[i];
      i-=i&-i;
    }
    return s;
  }
  void add(int i,int x){
    while(i<=n+1){
      bit[i]+=x;
      i+=i&-i;
    }
  }
};


int main(){
  int n;
  ll k,a[300000]={},s[300000]={};
  cin>>n>>k;
  FOR(i,1,n+1){
    cin>>a[i];
    a[i]-=k;
    a[i]+=a[i-1];
    s[i]=a[i];
  }
  sort(s+1,s+n+2);
  BIT b(n);
  ll ans=0;
  int x = lower_bound(s+1,s+n+2,0)-s;
  b.add(x,1);
  FOR(i,1,n+1){
    x = lower_bound(s+1,s+n+2,a[i])-s;
    ans += b.sum(x);
    b.add(x,1);
  }

  cout<<ans<<endl;

}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define PI 3.1415926535897932384626433832795
#define MOD 100000007
#define F first
#define S second
#define aLL(str) (str).begin(), (str).end()
#define IOS                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0)
#define ll long long
#define ld long double
#define lcm(a,b)     (a*b)/__gcd(a,b)
#define tr(s) for(auto it=v.begin();it!=v.end();it++)cout<<*it<<" ";
#define pv(a) for(ll i=0;i<a.size();i++) cout<<a[i]<<" ";
#define flu(i,a,b) for(ll i=a;i<b;i++)
#define blu(i,a,b) for(ll i=a;i>=b;i--)
typedef vector<ll> vl;
typedef map<ll,ll> ml;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
char e='\n';
ll i,j,le;

bool isPrime(int num){
    bool flag=true;
    for(int i = 2; i <= num / 2; i++) {
       if(num % i == 0) {
          flag = false;
          break;
       }
    }
    return flag;
}
int main()
{IOS;
int t;
t=1;
while(t--)
{ 
    ll l,r,d,c=0;
	cin>>l>>r>>d;
     flu(i,l,r+1)
	 {
		 if(i%d ==0)c++;
	 }
	 cout<<c<<e;
}
return 0;}



Measured memory_bytes: 3652
# coding: utf-8
import itertools
import math
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
List=[A,B,C,D,E]
ans=10000000
for i in itertools.permutations(List, 5):
    AList=list(i)
    R=0
    for i in range(5):
        if str(AList[i])[-1]!=0 and i!=4:
            R+=math.ceil((AList[i])/10)*10
        else:
            R+=AList[i]
    ans=min(ans,R)
    #print(AList)
    #print(ans)
print(ans)


Measured memory_bytes: 9068
#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main(){
	int n;cin>>n;
	vector<int> arrmv;
	for(int i=0;i<n;i++){
		int t;cin>>t;
		arrmv.push_back(t);
	}
	int maxele=-1;
	for(int i=0;i<(int)arrmv.size();i++){
		maxele=max(maxele,arrmv[i]);
		if(maxele-arrmv[i]>=2){cout<<"No"<<endl;
		return 0;}
	}
	cout<<"Yes"<<endl;
	return 0;
}


Measured memory_bytes: 1400
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

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

ll nCm(ll n, ll m){
    if(m == 0 || m == n){
        return 1;
    } else if(m == 1){
        return n;
    }
    return (nCm(n - 1, m) + nCm(n - 1, m - 1));
}

//-----------------------ここから-----------

int main(void){
    int n, m;
    cin >> n >> m;
    cout << (n - 1) * (m - 1) << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


def main():
    S=["D"] + list(input())
    N=len(S)
    MOD=10**9+7

    A = [0] * (N+1)
    C = [0] * (N+1)
    Q = [0] * (N+1)

    for i in range(1,N+1):
        s = S[i-1]
        A[i] = A[i-1]
        C[i] = C[i-1]
        Q[i] = Q[i-1]
        if s == "A":
            A[i] += 1
        elif s == "C":
            C[i] += 1
        elif s == "?":
            Q[i] += 1
    
    # print(A,C,Q)
    ans = 0
    for i in range(1,N+1):
        s = S[i-1]
        if s == "?" or s == "B":
            l_A = A[i-1]
            l_Q = Q[i-1]
            r_Q = Q[-1] - Q[i]
            r_C = C[-1] - C[i]

            
            
            # print(l_A,l_Q,r_Q,r_C)
            # ans += (l_A+l_Q) * (r_Q+r_C) % MOD

            left = pow(2,l_Q,MOD) * l_A % MOD
            if l_Q > 0:
                left += l_Q * pow((1+pow(2,MOD-2,MOD)), l_Q-1,MOD) * pow(2,l_Q-1,MOD) % MOD # 1個以上使うとき
                # print("r2",r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD)
                left %= MOD
                left += l_A * (pow(3,l_Q,MOD)-pow(2,l_Q,MOD)) % MOD 
                # print("r3",r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD)
                # print(right)

            right = pow(2,r_Q,MOD) * r_C % MOD # 一個も使わないとき
            # print("r",right)
            if r_Q > 0:
                right += r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD # 1個以上使うとき
                # print("r2",r_Q * pow((1+pow(2,MOD-2,MOD)), r_Q-1,MOD) * pow(2,r_Q-1,MOD) % MOD)
                right %= MOD
                right += r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD 
                # print("r3",r_C * (pow(3,r_Q,MOD)-pow(2,r_Q,MOD)) % MOD)
                # print(right)

            # exit()
            ans += left * right % MOD
            ans %= MOD
            # if s == "?":

            
    ans %= MOD
    print(ans)






if __name__ == "__main__":
    main()

Measured memory_bytes: 81984
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr            first
#define sc            second
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
using namespace std;
int main()
{
     ll a,b,v,w,t,dis,pos,con;
     cin>>a>>v>>b>>w>>t;
     dis=abs(a-b);
     pos=v*t;
     con=dis+w*t;
     if(pos>=con)
          cout << "YES\n";
     else cout << "NO\n";
}



Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

const ll INF = 1e9;
const long long INFL = 1LL<<60;

constexpr ll mod = 1000000007;

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

  vector<int> count(3, 0);

  ll ans = 1;

  rep(i, n) {
    int num = 0;
    for (auto& x : count) if (x == a[i]) num++;
    ans *= num;
    ans %= mod;
    for (auto& x : count) if (x == a[i]) {
      x++;
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3800
from math import sqrt, floor

def solve(x):
    p1s = [2, 3, 5, 7]
    if x in p1s:
        return x
    maxp = 100003
    l = p1s + [i for i in range(11, maxp + 1, 2) if i % 3 != 0 and i % 5 != 0 and i % 7 != 0]
    num = x
    if num % 2 == 0:
        num += 1
    while True:
        if all(num % m != 0 for m in l if m < floor(sqrt(num))):
            return num
        num += 2

_x = int(input())
print(solve(_x))


Measured memory_bytes: 4104
#include <stdio.h>

int main(){
	long long int input, total = 0;
	
	scanf ("%lld", &input);
	
	for (int i = 1; i <= input; i++){
		if(i % 3 != 0 && i % 5 != 0){
        total += i;
    	}
	}
	
	printf ("%lld", total);
	return 0;
}

Measured memory_bytes: 1732
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const ll INF = LONG_LONG_MAX / 2;

int N;
vector<ll> as;
vector<ll> bs;

int main(void) {
    cin >> N;

    ll sum = 0;

    as.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> as[i];
        as[i] -= (i + 1);
        sum += as[i];
    }

    // printf("sum: %lld\n", sum);

    bs = as;
    sort(bs.begin(), bs.end());

    ll b = bs[N / 2];
    // printf("b: %lld\n", b);
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += abs(bs[i] - b);
    }
    cout << ans << endl;

    return 0;
}


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

int main() {
    int A[3];
    std::cin >> A[0] >> A[1] >> A[2];

    if ((A[0] + A[1] + A[2]) >= 22) {
        std::printf("bust\n");
    } else {
        std::printf("win\n");
    }   

    return 0;
}


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

int main(){


	int a,b,c,x,y,sum;
	cin>>a>>b>>c>>x>>y;

	if(a+b>2*c){
	
		sum = 2*c*min(x,y);


		if(x-min(x,y)!=0){
			if(2*c<a){
				sum = sum +2*c*(x-y); 
			}else{
				sum = sum + a*(x-y);
			}
		}
		
	
		if(y-min(x,y)!=0){
			if(2*c<b){
				sum = sum +2*c*(y-x); 
			}else{
				sum = sum + b*(y-x);
			}
	
		}
	
	}else{
		sum= a*x+b*y;
	}

	cout<<sum<<endl;

}






Measured memory_bytes: 256
#include<stdio.h>//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=jp
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#include "bits/stdc++.h"
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	while(1){
		int n,w,d;
		scan(n>>w>>d);
		if(n+w+d==0) break;
		vector<pair<pint,pint> > WD;
		WD.push_back({{-1,w*d},{w,d}});
		rep(i,n){
			int p,s;
			scan(p>>s);
			p--;
			sort(WD.begin(),WD.end());
			int yoko=WD[p].second.first,tate=WD[p].second.second;
			int nagasa=s%(2*(yoko+tate));
			if((nagasa<yoko)^(nagasa<yoko+tate)^(nagasa<2*yoko+tate)){
				int newyoko1=nagasa%(yoko+tate);
				int newyoko2=yoko-newyoko1;
				WD[p]={{i,newyoko1*tate},{newyoko1,tate}};
				WD.push_back({{i,newyoko2*tate},{newyoko2,tate}});
			}
			else{
				int newtate1=(nagasa-yoko)%(yoko+tate);
				int newtate2=tate-newtate1;
				WD[p]={{i,newtate1*yoko},{yoko,newtate1}};
				WD.push_back({{i,newtate2*yoko},{yoko,newtate2}});
			}
		}
		vint menseki;
		for(auto x:WD){
			menseki.push_back(x.first.second);
		}
		sort(menseki.begin(),menseki.end());
		for(int i=0;i<menseki.size();i++){
			if(i!=0) printf(" %d",menseki[i]);
			else printf("%d",menseki[i]);
		}
		kaigyo;
	}

	return 0;
}



Measured memory_bytes: 3144
#include<iostream>
#include<algorithm>
#include<vector>
#include <numeric>
using namespace std;
int main(int argc, char const *argv[]) {
    int K;
    long long A,B;
    long long bis=1;
    std::cin >> K>>A>>B;
    if(B-A<=1){
        std::cout << 1+K << '\n';
    }else{
        if(bis<A){
            K-=A-bis;
            if(K<=0){
                bis+=K;
                std::cout << bis << '\n';
                return 0;
            }
            bis+=A-bis;
        }
        if(K%2==1){
                bis++;
        }
        bis+=(B-A)*(K/2);
        std::cout << bis << '\n';
                }
    return 0;
}

Measured memory_bytes: 256
N=int(input())
K=int(input())
x=list(map(int,input().split()))
    

A=0
B=0
C=0

for i in range(N):
    A=2*x[i]
    B=2*abs(K-x[i])
    if A<=B:
        C=C+A
    else:
        C=C+B
        
print(C)

Measured memory_bytes: 3064
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, k;
vector < int > h = {2, 4, 5, 7, 9};
vector < int > p = {3};


int main () {
	SpeedForce;

	string s;
	cin >> s;
	n = s.back() - '0'; 
	for (auto it : h) if (it == n) {
		cout << "hon\n";
		exit(0);
	}
	if (n == 3) {
		cout << "bon\n";
	} else {
		cout << "pon\n";
	}

	

	return Accepted;
}

// B...a

Measured memory_bytes: 3656
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<vector>
using namespace std;

signed main() {
	char a, b; cin >> a >> b;
	if (a > b)puts(">");
	else if (a < b)puts("<");
	else puts("=");
}

Measured memory_bytes: 256
console.log((args=>{
  const s = args.trim();
  const L = s.length;
  const p = Array(L).fill(0);
  for ( let i = L; --i;) p[i-1] = p[i] + (s[i]==='p');
  let g = 0, w = 0;
  for ( let i = 0; i < L; i++ ) {
    if ( s[i] === 'g' ) {
      if ( g > p[i] ) {
        g--; w++;
      } else g++;
    } else g--;
  }
  return `${w}`;
})(require('fs').readFileSync('/dev/stdin', 'utf8')));


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

/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);

ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;

const double PI = 2 * acos(0);

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;

set<int> valid;
char buf[100005];
int n;

int nextC;
void dfs(int curr, int sz) {
  if(sz == 1) return;
  set<int>::iterator it = valid.lower_bound(sz);
  it--;
  int nextSz = *it;
  int childrenLeft = sz - nextSz - 1;
  printf("%d %d\n", curr, ++nextC);
  dfs(nextC, nextSz);
  while(childrenLeft--) {
    printf("%d %d\n", curr, ++nextC);
  }
}

int main() {
  scanf("%s", buf);
  n = strlen(buf);
  for(int i = 0; i < n; i++) {
    if(buf[i] == '1') {
      valid.insert(i+1);
    }
  }
  if(valid.count(n)) {
    printf("-1\n");
    return 0;
  }
  if(!valid.count(1) || !valid.count(n-1)) {
    printf("-1\n");
    return 0;
  }
  for(int out: valid) {
    if(!valid.count(n-out)) {
      printf("-1\n");
      return 0;
    }
  }
  nextC = 1;
  dfs(1, n);
}


Measured memory_bytes: 9344
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>

#define isNum(a) (a >= '0' && a <= '9')
#define SP putchar(' ')
#define EL putchar('\n')
#define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)

template<class T>
void read(T&);
template<class T>
void write(const T&);

typedef long long ll;
typedef const long long & cll;
typedef const int & ci;
typedef std::pair<int, int> pii;
const int iinf = 2147483647;
const ll llinf = 9223372036854775807ll;
using std::min;
using std::max;
using std::abs;
using std::sort;

int main () {
  int a, b;
  read(a), read(b);
  if (b == 1) {
    write(0), EL;
    return 0;
  }
  --a, --b;
  write((b - 1) / a + 1), EL;
  return 0;
}

template<class T>
inline void read(T &Re) {
  T k = 0;
  char ch = getchar();
  int flag = 1;
  while (!isNum(ch)) {
    if (ch == '-') {
      flag = -1;
    }
    ch = getchar();
  }
  while (isNum(ch)) {
    k = (k << 1) + (k << 3) + ch - '0';
    ch = getchar();
  }
  Re = flag * k;
}
template<class T>
inline void write(const T &Wr) {
  if (Wr < 0) {
    putchar('-');
    write(-Wr);
  } else {
    if (Wr < 10) {
      putchar(Wr + '0');
    } else {
      write(Wr / 10);
      putchar((Wr % 10) + '0');
    }
  }
}


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

int main() {
  int h, w, d;
  cin >> h >> w >> d;
  vector<int> row(h * w, -1);
  vector<int> col(h * w, -1);
  for (int r = 0; r < h; ++r) {
    for (int c = 0; c < w; ++c) {
      int a;
      cin >> a;
      row[a - 1] = r;
      col[a - 1] = c;
    }
  }

  vector<int> costs(h * w, 0);
  for (int i = 0; i < d; ++i) {
    for (int x = i + d, y = i; x < h * w; y = x, x += d) {
      costs[x] = costs[y] + abs(row[x] - row[y]) + abs(col[x] - col[y]);
    }
  }

  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    cout << (costs[r - 1] - costs[l - 1]) << "\n";
  }

  return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;

ll N, x;

void solve() {
    cin >> N >> x;
    int L = 2*N-1;
    if (x == 1 || x == L) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        vi ans;
        REP(i,1,L/2+1) if (i != x) ans.push_back(i);
        if (ans.size() < L/2) ans.push_back(L/2+1);
        reverse(ans.begin(), ans.end());
        ans.push_back(x);
        for (int i = L; i >= L/2+2; --i) if (i != x) ans.push_back(i);
        if (ans.size() < L) ans.push_back(L/2+1);
        rep(i,L) cout << ans[i] << " ";
        cout << endl;
    }
}

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


Measured memory_bytes: 2420
using System;
class p
{
  static void Main()
  {
    int N = int.Parse(Console.ReadLine());
    string[] input = Console.ReadLine().Split(' ');
    int max = int.MinValue;
    int min = int.MaxValue;
    for (int i = 0; i < N; i++) {
      int a = int.Parse(input[i]);
      max = Math.Max(a, max);
      min = Math.Min(a, min);
    }
    Console.WriteLine(max - min);
  }
}

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

int main() {
    int A, B, C;
    while (cin >> A >> B >> C && (A || B || C)) {
        int t = 1e9;
        t = min(t, A * A + B * B);
        t = min(t, B * B + C * C);
        t = min(t, C * C + A * A);
        int n, R;
        cin >> n;
        for (int i=0; i<n; ++i) {
            cin >> R;
            if (t < 4 * R * R) {
                cout << "OK" << endl;
            } else {
                cout << "NA" << endl;
            }
        }
    }
    return 0;
}

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

int main() {
	ll n;
	cin >> n;
	map<ll,ll>m;
	ll ans(0);
	rep(i, n) {
		ll buf;
		cin >> buf;
		m[buf]++;
		ans += buf;
	}
	
	ll q;
	cin >> q;
	vector<ll>qans(q);
	rep(i, q) {
		ll b, c;
		cin >> b >> c;
		ll cnt = m[b];
		ans -= ll(b) * ll(cnt);
		ans += ll(c) * ll(cnt);
		//cout << ans;
		qans[i] = ans;
		m[b] -= cnt;
		m[c] += cnt;

	}
	rep(i, q) {
		cout << qans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 9928
K, N = map(int, input().split())

A = [int(v) for v in input().split()]
sorted(A)

min_dist = K - (A[N - 1] - A[0])
for i in range(N - 1):
    d = A[i + 1] - A[i]
    min_dist = max(d, min_dist)

print(K - min_dist)



Measured memory_bytes: 24908
#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() {
	int A, B;
	cin >> A >> B;
	int amn=(25*A+1)/2, amx=(25*(A+1)+1)/2;
	int bmn=10*B, bmx=10*(B+1);
	if(max(amn, bmn)<min(amx, bmx)) cout << max(amn, bmn) << endl;
	else cout << -1 << endl;
	return 0;
}

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

using namespace std;

typedef pair<int, int> P_ii;
typedef pair<string, int> P_si;
typedef long long int ll;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const int MOD = 1000000007;
const int MAX = 100100;

int main() {
    ll X, Y;
    cin >> X >> Y;
    vector<ll> A;
    ll now = X;
    while (now <= Y) {
        A.push_back(now);
        now *= 2;
    }
    ll ans = A.size();
    printf("%lld\n", ans);
    return 0;
}



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

int main(){
    int n,m,i,j,k,count=0;

    cin >> n >> m;
	
    long h[n];
    int ans[n]={};
  	int a[m],b[m];

    for(i=0;i<n;i++){
        cin >> h[i];
    }
    
    for(j=0;j<m;j++){
        cin >> a[j] >> b[j];
      	if(h[a[j]-1]>h[b[j]-1]) ans[b[j]-1]=1;
      	else if(h[a[j]-1]==h[b[j]-1]){
          ans[a[j]-1]=1;
          ans[b[j]-1]=1;
        }
      	else ans[a[j]-1]=1;
    }

    for(i=0;i<n;i++){
        if(ans[i]==0) count++;
    }

    cout << count << endl;
}

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

int main(void){
    char str[128] = {0};
    int i, len;
    scanf("%[^\n]", str);
    len = strlen(str);

    for(i = 0; i < len; i++){
        if(str[i] >= 'a' && str[i] <= 'z'){
            str[i] -= 'a' - 'A';
        }
    }

    for(i = 0; i < len; i++){
        printf("%c", str[i]);
    }
    putchar('\n');
    return 0;
}

Measured memory_bytes: 524
//高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF INT_MAX
#define LLINF LLONG_MAX
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
    for (T& x: vec) { is >> x; }
    return is;
}
bool ch[100000] = {};
bool cheap[100000] = {};

int main() {
	ll ans = 0;
	ll tmp;
	//n頂点m枝に対して隣接リストをつくる。
	int n, m;
	cin >> n >> m;
	vector<pair<ll, int>> a(n);
	REP(i, n){
		cin >> tmp;
		a[i] = make_pair(tmp, i);
	}
	sort(a.begin(), a.end());
	
	int u, v;
	//vector< vector <int> > ls(n); //0-origin
	vector< vector <int> > ls(n+1); //1-origin
	REP(i, m){ 
		cin >> u >> v; 
		ls[u].push_back(v); 
		ls[v].push_back(u); //有向グラフならコメントアウトせよ
	}
	//
	//cout << n-m-1 << " " << n << endl;
	if((n - m -1)*2 > n) cout << "Impossible" << endl;
	else if(n-m-1 == 0) cout << 0 << endl;
	else{
		int co = 0;
		for(int i=0; i < n; i++){
			int here = a[i].second;
			int cost = a[i].first;
			if(!ch[here]){
				ans += cost;
				co++;
				cheap[here] = true;
				queue<int> q;
				q.push(here);
				while(!q.empty()){
					int now = q.front();
					q.pop();
					ch[now] = true;
					REP(j, (int)ls[now].size()){
						if(!ch[ls[now][j]]) q.push(ls[now][j]);
					}
				}
			}
		}
		for(int i=0; co < (n - m - 1)*2; i++){
			int here = a[i].second;
			int cost = a[i].first;
			if(!cheap[here]){
				//cout << cost << endl;
				ans += cost;
				co++;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 10564
#include <stdio.h>
int main(void)
{
    int n, i; 
    int a[1000]; 

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

    for(i = n - 1; i >= 1; i--){
        printf("%d ", a[i]);
    }
    printf("%d", a[0]);
    
    printf("\n");

    return 0;
}


Measured memory_bytes: 2060
n = gets.to_i
a_list = gets.split.map(&:to_i)
cnt = Hash.new(0)
a_list.each do |a|
  cnt[a] += 1
end
hen_cands = cnt.select{|k,v| v >= 2}.to_a.sort_by{|a| -a[0]}
if hen_cands.empty?
  puts 0
elsif hen_cands[0] && hen_cands.size == 1
  hen_cands[0][1] < 4 ? puts(0) : puts(hen_cands[0][0]**2)
else
  hen_cands[0][1] < 4 ? puts(hen_cands[0][0]*hen_cands[1][0]) : puts(hen_cands[0][0]**2)
end



Measured memory_bytes: 16776
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

void insert(int);
void inorder(Node);
void preorder(Node);
Node treeSearch(Node,int);
Node treeMinimum(Node);
Node treeSuccessor(Node);
void treeDelete(Node);

int main(){
  int n, i, x;
  char com[20];
  scanf("%d",&n);

  for (i=0;i<n;i++){
    scanf("%s",com);
    if(com[0]=='f'){
      scanf("%d",&x);
      Node t = treeSearch(root, x);
      if (t!=NIL) printf("yes\n");
      else printf("no\n");
    }
    
    else if(com[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }
    
    else if(com[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }

    else if(com[0]=='d'){
      scanf("%d",&x);
      treeDelete(treeSearch(root,x));
    }
  }

  return 0;
}


void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }
  z->parent=y;

  if(y==NIL) root=z;
  else if(z->key < y->key) y->left=z;
  else y->right=z;
}

void inorder(Node u){
  if(u!=NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }

}
void preorder(Node u){
  if(u!=NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}

Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
    
  if(k<u->key) return treeSearch(u->left,k);
  else return treeSearch(u->right,k);
  
}

Node treeMinimum(Node x){
  while(x->left!=NIL) x=x->left;
  return x;
}

Node treeSuccessor(Node x){
  Node y;
  
  if(x->right!=NIL) return treeMinimum(x->right);

  y=x->parent;
  while(y!=NIL && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y;
  Node x;

  if(z->left==NIL || z->right==NIL) y=z;
  else y=treeSuccessor(z);

  if(y->left!=NIL) x=y->left;
  else x=y->right;

  if(x!=NIL) x->parent=y->parent;
  
  if(y->parent==NIL) root=x;
  else if(y==y->parent->left) y->parent->left=x;
  else y->parent->right=x;

  if(y!=z) z->key=y->key;

  free(y);
  
}



Measured memory_bytes: 20452
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define MaxN 200000+100
using namespace std;
struct node
{
	int sum;
	int num;
}Node[MaxN]; 
bool cmp(struct node a,struct node b)
{
	return a.sum>b.sum;
}
int main()
{
	int N,K;
	scanf("%d %d",&N,&K);
	for(int i=0;i<MaxN;i++)
	{
//		Node[i].num=num;
		Node[i].sum=0; 
	} 
	for(int i=0;i<N;i++)
	{
		int num;
		scanf("%d",&num);
		Node[num].sum++; 
	}
	sort(Node,Node+MaxN,cmp);
	int sum=0;
	int now=0;
	while(Node[now].sum!=0)
		now++;
	for(int i=now-1;i>K-1;i--)
		sum+=Node[i].sum;
	printf("%d\n",sum);
	return 0;
 } 

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const ::std::uint_fast64_t MOD = 1e9+7;

class mint
{
private:
    using value_type = ::std::uint_fast64_t;
    value_type n;
public:
    mint():n(0){}
    mint(::std::int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ::std::ostream& operator<<(::std::ostream &os, const mint &a){
		return os << a.n;
	}
    friend ::std::istream& operator>>(::std::istream &is, mint &a){
        value_type temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    mint operator==(const mint &m) const {return n==m.n;}
    mint operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(value_type b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vll c(n);
    rep(i,n) cin>>c[i];
    sort(rall(c));

    mint ans=0;
    rep(i,n){
        mint A = mint(2).pow(i-1)*i + mint(2).pow(i);
        mint B = mint(2).pow(i+1)*mint(4).pow(n-i-1);
        mint C = A*B;
        ans += C*c[i];
    }
    cout<<ans<<endl;
    return 0;
}


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

#define Fast ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define FO freopen("in.txt", "r", stdin)
#define FC freopen("out.txt", "w", stdout)
#define aise cout<<"aise"<<endl
#define pb push_back
#define mp make_pair
#define ll long long
#define mset(v, a) memset(v, a, sizeof(v))
#define pll pair< ll, ll >
#define ff first
#define ss second
#define pi acos(-1.0)
#define mxN 100010
#define inf 1e9

int main()
{

    string ss, a = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    ll n;
    cin >> n >> ss;
    for(ll i = 0; i < ss.size(); i++)
    {
        if(ss[i]+n > 'Z')
            cout << char(ss[i]+n- 'Z' + 'A'-1);
        else cout << char(ss[i]+n);
    }
}


Measured memory_bytes: 256
#!/usr/bin/ruby

until (n = gets).nil?
  puts n.to_i.to_s(2).chars.map.with_index{|x, i| x.to_i.zero? ? nil : i }.reject{|x| x.nil? }.map{|x| 2**(n.to_i.to_s(2).size - x-1)}.reverse.join(?\s)
end

Measured memory_bytes: 6132