akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int const N = 100 * 1000 + 16;
int const inf = 1000 * 1000 * 1000;
int const M = inf + 7;

int n, m, q;
int a[2][N];
int b[2][N];
char S[N];
char T[N];

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  cin >> (S+1) >> (T+1) >> q;
  for(int i = 1; S[i]; ++i) {
    a[0][i] = S[i] == 'A';
    b[0][i] = 1 - a[0][i];
    n = i+1;
  }

  for(int i = 1; T[i]; ++i) {
    a[1][i] = T[i] == 'A';
    b[1][i] = 1 - a[1][i];
    m = i+1;
  }

  partial_sum(a[0], a[0] + n, a[0]);
  partial_sum(a[1], a[1] + n, a[1]);

  partial_sum(b[0], b[0] + n, b[0]);
  partial_sum(b[1], b[1] + n, b[1]);

  while(q--) {
    int l, r;
    cin >> l >> r;
    int x = 2*(a[0][r] - a[0][l-1])
            + (b[0][r] - b[0][l-1]);

    cin >> l >> r;
    int y = 2*(a[1][r] - a[1][l-1])
            + (b[1][r] - b[1][l-1]);


    if(abs(x-y) % 3 == 0)
      cout << "YES\n";
    else
      cout << "NO\n";
  }
  cout << flush;
}

Measured memory_bytes: 2304
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,ssse3,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
//using arr = array;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using vpi = vector<pi>;
using ld = long double;
const int maxn = 1<<12, mod = 998244353 , lg = 19;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll x = 12;//CHANGE TO 12
const ll full = (1<<x)-1;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string a = "Sunny", b = "Cloudy", c = "Rainy";
	string t;
	cin >> t;
	if(t==a) cout << b;
	if(t==b) cout << c;
	if(t==c) cout << a;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <limits>
#include <set>
#define MAX 100000
#define rep(i,s,N) for(int i=s;i<N;i++)
using namespace std;
typedef long long int lli;

int main(void)
{
	lli A, B; cin >> A >> B;
	if (A > B)swap(A, B);
	lli ans;
	if (A == 1 && B == 1)ans = 1;
	else if (A == 1 && B != 1)ans = B - 2;
	else ans = (A - 2)*(B - 2);
	
	cout << ans << endl;

	return 0;
}

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

int main()
{
	ll a,b,k;
	cin>>a>>b>>k;
	
	if(k<=a)
	{
		a -=k;
		
	}

	else if(k>a)
	{
		ll l=k-a;
		a = 0;
		
			if(l<=b)
	{
		b -=l;
		
	}

	else if(l>b)
	{
		b = 0;
	}
	}
	cout<<a<<" "<<b;
}

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

int main() {
    using namespace std;
    ios_base::sync_with_stdio(false);

    int N;
    cin >> N;

    vector vec(N-1, 0);
    vector a(N, 0);
    for(auto & v: vec) 
    {
        cin >> v;
        a[max(v - 1, 0)] += 1;
    }

    for(auto & asw: a) 
    {
        cout << asw << '\n';
    }
}

Measured memory_bytes: 4840
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    int weight;
    edge * next;
};
edge * new_edge()
{
    static edge a[400005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
void inserts(int x,int y,int z)
{
    edge * t=new_edge();
    t->y=y;
    t->weight=z;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y,int z)
{
    inserts(x,y,z);
    inserts(y,x,z);
}
priority_queue<pair<long long,int> > q;
long long dist[100005];
int dp[100005];
long long dis[100005];
int dp2[100005];
const int modo=1000000007;
bool vis[100005];
void dijkstra(int s)
{
    q.push(make_pair(0,s));
    memset(dist,-1,sizeof(dist));
    memset(dp,0,sizeof(dp));
    memset(vis,false,sizeof(vis));
    dp[s]=1;
    dist[s]=0;
    for (;!q.empty();)
    {
        int x=q.top().second;
        q.pop();
        if (vis[x]) continue;
        vis[x]=true;
        edge * t;
        for (t=li[x];t!=0;t=t->next)
        {
            if (dist[t->y]==dist[x]+t->weight)
            {
                dp[t->y]=(dp[t->y]+dp[x])%modo;
            }
            if ((dist[t->y]>dist[x]+t->weight)||(dist[t->y]==-1))
            {
                dp[t->y]=dp[x];
                dist[t->y]=dist[x]+t->weight;
                q.push(make_pair(-dist[t->y],t->y));
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int s,t;
    scanf("%d%d",&s,&t);
    s--;
    t--;
    int i;
    for (i=0;i<m;i++)
    {
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        x--;
        y--;
        insert_edge(x,y,d);
    }
    dijkstra(t);
    memcpy(dis,dist,sizeof(dis));
    memcpy(dp2,dp,sizeof(dp2));
    long long val=dis[s];
    dijkstra(s);
    int ans=(long long)dp[t]*dp[t]%modo;
    for (i=0;i<n;i++)
    {
        if (dist[i]+dis[i]!=val) continue;
        if (dist[i]==dis[i])
        {
            ans-=(long long)dp[i]*dp2[i]%modo*dp[i]%modo*dp2[i]%modo;
            ans%=modo;
        }
        edge * t;
        for (t=li[i];t!=0;t=t->next)
        {
            if (dist[t->y]+dis[t->y]!=val) continue;
            if (dist[i]+t->weight!=dist[t->y]) continue;
            if (dist[i]*2>=val) continue;
            if (dist[t->y]*2<=val) continue;
            ans-=(long long)dp[i]*dp2[t->y]%modo*dp[i]%modo*dp2[t->y]%modo;
            ans%=modo;
        }
    }
    ans+=modo;
    ans%=modo;
    printf("%d\n",ans);
    return 0;
} 


Measured memory_bytes: 11504
import math

p = [True] * (10**5 + 1)

p[0] = False
p[1] = False
i = 2
while i * i <= 10**5:
    if p[i]:
        n = i * 2
        while n <= 10**5:
            p[n] = False
            n += i
    i += 1

s = [0] * (10**5 + 2)
for i in range(2, 10**5 + 2):
    s[i] = s[i - 1] + (1 if (p[i - 1] and p[i // 2]) else 0)

q = int(input())
l = [0] * q
r = [0] * q

for i in range(0, q):
    l[i], r[i] = [int(i) for i in input().split(" ")]

for i in range(0, q):
    print(s[r[i] + 1] - s[l[i]])

Measured memory_bytes: 15544
<?php
  list($n, $m) = explode(" ", trim(fgets(STDIN)));

  $dp = [];

  $a = [];
  for($i=0; $i<$n; $i++){
    list($x, $y) = explode(" ", trim(fgets(STDIN)));
    //if(!isset($a[$x])){
    //  $a[$x] = [];
    //}
    $a[$x][] = $y;
  }

  $ans = 0;
  $p = new SplMaxHeap();
  for($i=1; $i<=$m; $i++){
    if(isset($a[$i])){
      foreach($a[$i] as $v){
        $p->insert($v);
      }
    }
    if(!$p->isEmpty()){
      $ans += $p->extract();
    }
  }

  echo $ans;

Measured memory_bytes: 51700
#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, d;
	cin >> n >> d;
	vector<vector<float>> za(n,  vector<float>(d));
	rep(i, n){
    	rep(j, d){
    		cin >> za.at(i).at(j);
        }
    }
	float ans = 0;
	float ans2 = 0;
	int cou = 0;
	rep(i, n){
    	rep(j, n){
        	if(i != j){
	        	ans = 0;
            	rep(k, d){
            		ans += pow(za.at(i).at(k) - za.at(j).at(k), 2);
                }
            	ans2 = floor(sqrt(ans));
             	ans = sqrt(ans);
            	if(ans2+0.00000001 > ans && ans2-0.00000001 < ans){
                	cou++;
                }
            }
        }
    }
	cout << cou/2 << endl;
}

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

#ifndef DEBUG
#define endl '\n'
#define debug(...)
#else
#define debug(...) __VA_ARGS__
#endif
#define debugf(...) debug(printf(__VA_ARGS__);)

const int N = 2e5 + 5;

int a[N];



int (((((main)))))() <%
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;

    int id = 1;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] == id) {
            id++;
        } else {
            ans++;
        }
    }

    cout << (ans == n ? -1 : ans) << endl;

    return 0;
%>

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		if(a<b && b<c) System.out.println("Yes");
		else System.out.println("No");

	}

}

Measured memory_bytes: 26036
#include<stdio.h>
#define N 200000

int main()
{
  int n,i;
  int R[N];
  int Min,Max;
  
  scanf("%d",&n);

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

  Min = R[0];
  Max = R[1]-R[0];

  for(i=1; i<n; i++){
    if((R[i]-Min) > Max)
      Max = R[i]-Min;
    if(Min > R[i])
      Min = R[i];
  }

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



Measured memory_bytes: 2604
//#pragma region ALL(include define etc)
#include <iostream>   // swap(a, b)
#include <string>
#include <cmath>      // abs(絶対値) sin cos tan(角度 / 180.0 * 3.141592)
#include <vector>     // vec.push_back(a) vec.pop_back()
#include <algorithm>  // max(a, b) min(a, b) reverse() sort()
#include <functional> // sort(a, a + N, greater<型>());
#include <math.h>
#include <iomanip>
#define int long long
#define ll long long
//#define double long double
using namespace std;
//#pragma endregion

signed main()
{
	//int x;

	//int N;
	//int n;
	//int m;
	//int k;
	//string s;
	//string t;
	//int m1, m2;
	//int a, b, c, k;

	//long double aaa;

	//int k, d;
	//int all = 0;
	double all;
	double a, b;
	double h, m;
	//int a[30000] = { 0 };
	double c, d, e;

	double mbox, hbox;
	double box, box2;

	//int b = 0;

	//int box[10000] = { 0 };

	//bool flag = true;

	//string str;

	cin >> a >> b >> h >> m;
	//cin >> s;

	//n = N % 10;

	c = (double)h * 30.0;
	d = (double)m * 0.5; // x分で進む角度（時針）
	hbox = c + d; // 時針の角度

	mbox = 6.0 * m; //分針の角度

	if (hbox > mbox)
	{
		box = hbox - mbox;
	}
	else if (mbox > hbox)
	{
		box = mbox - hbox;
	}
	else
	{
		box = 0.0;
	}

	if (box >= 180.0)
	{
		box = 360.0 - box;
	}

	//box2 = subMain(box);
	box2 = box * 3.14159265358979323846 / 180.0; // ラジアンに変換

	all = (a * a) + (b * b) - (2.0 * a * b * cos(box2));

	//cout << endl;
	//for (int i = 0; i <= (k - 2); i++)
	//{
	//	b = a[b];
	//	//cout << b << "\n";
	//}
	/*if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9)
	{
		cout << "hon\n";
	}
	else if (n == 0 || n == 1 || n == 6 || n == 8)
	{
		cout << "pon\n";
	}
	else
	{
		cout << "bon\n";
	}*/

	/*if (k >= b)
	{
		cout << s << "\n";
	}
	else
	{
		for (int i = 0; i < k; i++)
		{
			cout << s[i];
		}
		cout << "...\n";
	}*/
	
	//cout << b << "\n";

	/*if (flag == true)
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}*/

	all = pow(all, 0.5);

	cout << fixed << setprecision(111) << all;
}

Measured memory_bytes: 4356
#include<iostream>
using namespace std;
void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;
    l_hold = left;
    r_hold = right;
    pivot = numbers[left];
    while (left < right)
    {
        while ((numbers[right] >= pivot) && (left < right))
            right--;
        if (left != right)
        {
            numbers[left] = numbers[right];
            left++;
        }
        while ((numbers[left] <= pivot) && (left < right))
            left++;
        if (left != right)
        {
            numbers[right] = numbers[left];
            right--;
        }
    }
    numbers[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;
    if (left < pivot)
        q_sort(numbers, left, pivot-1);
    if (right > pivot)
        q_sort(numbers, pivot+1, right);
}
int main()
{
	int mountain[10];	
	for(int i=0;i<10;i++)
		cin>>mountain[i];
	q_sort(mountain,0,9);
	for(int i=9;i>6;i--)
		cout<<mountain[i]<<endl;
}

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

using namespace std;

int main(){
  int H,W; cin >> H >> W;
  int N; cin >> N;
  vector<int>A(N);for(int i = 0; i < N;i++){ cin >> A[i];}
  vector<int> B;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < A[i]; j++){
      B.push_back(i+1);}} 
  sort(B.begin(),B.end());
  
  vector<vector<int>> C(H,vector<int>(W));
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      C[i][j] = B[i*W + j];}}
  
  vector<vector<int>> D(H,vector<int>(W));
  
  for(int i = 0; i < H; i++){
      for(int j = 0; j < W; j++){
       if(i % 2 == 1) {D[i][j] = C[i][W-1-j];}
       else{D[i][j] = C[i][j];}}}
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cout << D[i][j] << ' ';}
    cout << endl;}
  return 0;}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define Int int64_t
#define dump(x) cout << (x) << endl
#define fi first
#define se second
Int mod = 1e9+7;
//Int mod = 998244353;
Int INF = 1e18;
double EPS = 0.00000001;

int main() {
    Int n;
    cin >> n;
    if (n == 1) {
        printf("%lf\n", 1.0);
    }
    else if (n % 2 == 0) {
        printf("%lf\n", 0.5);
    }
    else {
        double x = n;
        printf("%lf\n", (double)(n / 2 + 1) / x);        
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

ll N,M;
vector<int> g[100100];
ll dp[100100]={0};
bool used[100100];

ll dfs(int s){
  if(used[s]) return dp[s];
  for(auto t:g[s]){
    dp[s]=max(dp[s],dfs(t)+1);
  }
  used[s]=true;
  return dp[s];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> M;
  ll x,y;
  for(int i=1;i<=M;i++){
    cin >> x >> y;
    g[x].push_back(y);
  }
  ll ans=0;
  for(int i=1;i<=N;i++){
    ans= dfs(i);
  }
  for(int i=1;i<=N;i++){
    ans=max(ans,dp[i]);
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

const int MOD = 1e9 + 7;
void add(int &res, int x) {
  res += x;
  if (res >= MOD) res -= MOD;
}

int n;
int adj[22][22];
int memo[22][1 << 21];
int dp(int i, int mask) {
  int &res = memo[i][mask];
  if (res != -1) return res;
  if (i == n) return res = 1;
  res = 0;
  for (int j = 0; j < n; j++) {
    if (adj[i][j] && ((1 << j) & mask)) {
      add(res, dp(i+1, mask ^ (1 << j)));
    }
  }

  return res;
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        cin >> adj[i][j];
    
    memset(memo, -1, sizeof memo);
    cout << dp(0, (1 << n) - 1) << endl;;
}


Measured memory_bytes: 180480
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define in insert
#define rep(i,a,b) for(int i = a ; i < b ; i++)
#define repr(i,a,b) for(int i = b ; i > a ; i--) 

int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
      
}   
 
signed main(){
    fast;
    int ans=100, d=0;
    int x; cin >> x;
    while(ans<x){
        ans= (1.01*ans);
        d++;
    }
    cout << d;
}

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

using namespace std;
using ll = long long;

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

    int d;
    cin >> d;
    vector<int> c(26), t(d);
    vector<vector<int>> s(d, vector<int>(26));
    for(int i = 0; i < 26; ++i) cin >> c[i];
    for(int j = 0; j < d; ++j)
        for(int i = 0; i < 26; ++i) cin >> s[j][i];
    for(int j = 0; j < d; ++j) {
        cin >> t[j];
        t[j]--;
    }

    int score = 0;
    vector<int> blank(26);

    for(int j = 0; j < d; ++j) {
        score += s[j][t[j]];
        for(int i = 0; i < 26; ++i) {
            if(i == t[j]) {
                blank[i] = 0;
            } else {
                blank[i]++;
                score -= c[i] * blank[i];
            }
        }
        printf("%d\n", score);
    }


    return 0;
}

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

void insertionSort(long long A[], int N, int g, int &count){
    int i, j;
    for(i=g; i<N; ++i){
        long long tmp = A[i];
        j = i -g;
        while(j >= 0 && A[j] > tmp){
            A[j + g] = A[j];
            j -= g;
            count++;
        }
        A[j+g] = tmp;
    }
}

int main(){
    int cnt = 0;
    int n; cin >> n;
    long long arr[n];
    for(int i = 0 ; i < n; i++){
        cin >> arr[i];
    }
    int m = 0;
    int test = n;
    while(test > 0){
        test = (test-1)/2;
        m++;
    }
    int G[m];
    for(int i = 0; i< m; i++){
        G[i] = pow(2, m-1-i);
    }
    for(int i =0; i < m; ++i){
        insertionSort(arr, n, G[i], cnt);
    }
    cout << m << endl;
    for(int i = 0; i < m; ++i) cout << G[i] <<((i != m - 1) ? " ": "");
    cout << endl;
    cout << cnt << endl;
    for(int i =0; i < n; ++i){
        cout << arr[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 10904
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define MAX 200005

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


ll h, ans=0;

ll attack(ll hp){
  if(hp>1){
    ll ansr=ans;
    attack(hp/2);
    ans+=ans-ansr;
  }
  ans++;
}

int main(){
  cin >> h;
  cout << attack(h) << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int N=gi();
	    List<Edge>[] E=new ArrayList[N];
	    for (int i=0; i<N;i++) {
	    	E[i]=new ArrayList<Edge>();
	    }
	    for (int i=0; i<N-1;i++) {
	    	int a=gi()-1;
	    	int b=gi()-1;
	    	long c=gl();
	    	E[a].add(new Edge(a,b,c));
	    	E[b].add(new Edge(b,a,c));
	    }

	    int Q=gi();
	    int K=gi();

	    long[] d=new long[N];
	    for (int i=0; i<N;i++) {
	    	d[i]=Long.MAX_VALUE;
	    }
	    d[K-1]=0;
	    PriorityQueue<Pair<Long, Integer>> que=new PriorityQueue<Pair<Long, Integer>>();
	    Pair<Long, Integer> sp= new Pair<Long, Integer>(0l,K-1);
        que.add(sp);
	    while(!que.isEmpty()) {
	    	Pair<Long, Integer> p=que.poll();
	    	int v=p.getValue();
	    	if(d[v]<p.getKey())continue;
	    	for(int i=0; i<E[v].size();i++) {
	    		Edge e=E[v].get(i);
	    		if(d[v] != Long.MAX_VALUE && d[e.to]>d[v]+e.cost) {
	    			d[e.to]=d[v]+e.cost;
	    			que.add(new Pair<Long, Integer>(d[e.to], e.to));
	    		}
	    	}
	    }

	    StringBuilder sb=new StringBuilder();
	    for(int i=0; i<Q;i++) {
	    	int x=gi()-1;
	    	int y=gi()-1;
	    	long ans=d[x]+d[y];
	    	sb.append(ans);
	    	sb.append(System.lineSeparator());
	    }

	    System.out.println(sb);


        //System.out.println(ns);
	}

	public static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> implements Comparable<Pair<K, V>> {
		/** serialVersionUID. */
	    private static final long serialVersionUID = 6411527075103472113L;

	    public Pair(final K key, final V value) {
	        super(key, value);
	    }

		@Override
		public int compareTo(Pair<K, V> o) {

			Comparable key = (Comparable)this.getKey();
			Comparable key2 = (Comparable)o.getKey();

			return key.compareTo(key2);
		}

	}

	public static class Edge {
	    private int from;
	    private int to;
	    private long cost;

	    public Edge(int f, int t, long c) {
	    	this.from=f;
	    	this.to=t;
	    	this.cost=c;
	    }
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 84748
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod;
#define chmax(a,b) a=max(a,b);
#define N 100010
ll cnt[16],t[N];
ll f[(1<<16)][16];
int main(){
  ll n; cin>>n;
  for(int i=0;i<n;i++)t[i]=0;
  for(int i=0;i<n-1;i++){
      ll a,b,c;cin>>a>>b>>c;
      t[a]^=c;
      t[b]^=c;
  }
  for(int i=0;i<16;i++)cnt[i]=0;
  for(int i=0;i<n;i++)cnt[t[i]]++;
  ll ans=cnt[0]; cnt[0]=0;
  for(int i=1;i<16;i++){
      ans+=(cnt[i]/2);
      cnt[i]%=2;
      //cout<<i<<":"<<cnt[i]<<endl;
  }
  ll ma=0;
  for(int i=0;i<(1<<16);i++)for(int j=0;j<16;j++)f[i][j]=0;
  f[0][0]=0;
  for(int i=0;i<(1<<16);i++)for(int j=0;j<16;j++){
      ma=max(ma,f[i][j]);
      for(int k=0;k<16;k++)if(((i>>k)&1)==0&&cnt[k]>0){
	  chmax(f[i+(1<<k)][j^k],f[i][j]+(j==k));
      }
  }
  ans+=ma;
  cout<<n-ans<<endl;
  return 0;
}


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

result, md = 0, len("{:b}".format(K))
for n in range(1, N + 1):
	d, x = 0, n
	while x < K:
		d += 1
		x *= 2
	#print(md, n, d)
	result += (1 / N) * (1 / 2)**d
print(result)


Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int l = sc.nextInt();
        int[][] A = new int[n][m];
        int[][] B = new int[m][l];
        long[][] C = new long[n][l];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                A[i][j] = sc.nextInt();
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < l; j++){
                B[i][j] = sc.nextInt();
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < l; j++){
                long sum = 0;
                for(int k = 0; k < m; k++){
                    sum += A[i][k] * B[k][j];
                }
                C[i][j] = sum;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < l; j++){
                System.out.print(C[i][j]);
                if(j != l - 1){
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}


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

int main () {
  int N;
  cin >> N;
  int sum = 0;
  int ave;
  int ans = 0;
  vector<int>a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
    sum += a.at(i);
  }
  double M = sum*1.0/N;
  ave = round(M);
  for (int i = 0; i < N; i++) {
    ans += (ave-a.at(i))*(ave-a.at(i));
  }
  cout << ans << endl;
}
  
    
   

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define long long long
#define ull unsigned long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define pb push_back
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define V vector
#define debug(X) cerr<< #X << " = " <<X << endl
#define debug2(X,Y) cerr<< #X << " = " <<X << ","<<#Y<<" = "<<Y<<endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar

using namespace std;

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }
int n,m,f[100010];
void input()
{
    cin>>n>>m;
    up(i,1,m)
    {
    	int u,v; cin>>u>>v;
    	f[u]++; f[v]++;
    }
    up(i,1,n)
     if (f[i]%2==1)
	 {
	 	cout<<"NO"; return;
	 };

    cout<<"YES";
}

void solve()
{

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);// don't use when interactive
    #define TASK "tmp"
   // freopen(TASK".inp","r",stdin);
   // freopen(TASK".out","w",stdout);

    input();
    solve();

    return 0;
}


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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    ll X,Y;
    cin>>X>>Y;
    if(abs(X-Y)<=1) cout<<"Brown"<<endl;
    else cout<<"Alice"<<endl;   
}

Measured memory_bytes: 3636
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a > b) {
			System.out.println("a > b");
		} else if (a < b) {
			System.out.println("a < b");
		} else {
			System.out.println("a == b");
		}
		sc.close();
	}

}



Measured memory_bytes: 26352
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
#include <utility>
using namespace std;

int f(int n){
    int ret;
    if(n % 2 == 0){
        ret = n / 2;
    }else{
        ret = 3 * n + 1;
    }
    return ret;
}
int main()
{
    int s;
    cin >> s;
    int val = s;
    if(val == 2 || val == 1){
        cout << 4;
    }
    else{
        for(auto i = 1; i < 1000000; ++i){
            if(val == 4){
                cout << i + 3;
                break;
            }
            val = f(val);
        }
    }
    return 0;
}



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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[2005];
ll dp[2005][2005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, X;
    cin >> N >> X;
    REP(i, N) {
        cin >> A[i];
    }

    ll mx = 0;
    REP(i, N) {
        ll mn = A[i];
        REP(j, N) {
            mn = std::min(mn, A[(N + i - j) % N]);
            dp[i][j] = mn;
        }
    }

    ll ans = INF;
    REP(i, N) {
        ll s = i * X;
        REP(j, N) {
            s += dp[j][i];
        }
        ans = std::min(ans, s);
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;
int main() {
    string s, t, u;
    int a, b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s.compare(u)==0)cout << a - 1 << ' ' << b << endl;
    else cout << a << ' ' << b - 1 << endl;
}

Measured memory_bytes: 256
/*D - Caracal vs MOnster*/
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    
    long long monsters = 1ll;
    long long health;
    cin >> health;
    long long aux = 1ll;
    
    while(health > 1ll){
      
        health /= 2ll;
        aux *= 2ll;
        monsters += aux; 
        
    }
    
    cout << monsters;
    
    return 0;
}

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

signed main()
{
    
   int n;
   cin>>n;
   int s=0;
   for(int i=1;i<=n;i++)
   {
       if(i%3==0 || i%5==0)
       continue;
       s+=i;
   }
   cout<<s;
    
   
}



Measured memory_bytes: 3600
// ------------------------------------
// Date:2018/ 2/23
// Problem:ABC 046 AtCoDeerAndElectionReport c.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()

using ll = long long;

#define MOD 1000000007

int main()
{
  int N;
  ll currentT,currentA,lastT,lastA,tmp;
  lastT = lastA = 1;
  cin >> N;
  REP(i,N) {
    cin >> currentT >> currentA;
    // 保持したlastTとlastAのうち大きい方をかけて上書き
    tmp = max(lastT/currentT + (lastT%currentT==0?0:1),
              lastA/currentA + (lastA%currentA==0?0:1));
    lastT = tmp*currentT;
    lastA = tmp*currentA;
  }
  cout << lastA+lastT << endl;
  return 0;
}



Measured memory_bytes: 256
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
A = inpl()

if len(A) <= 2:
    ans = max(A)
else:
    gcd_left = [A[0]]
    gcd_right = [A[N-1]] 
    for i in range(N-1):
        gcd_left.append(gcd(gcd_left[i],A[i+1]))
        gcd_right.append(gcd(gcd_right[i],A[N-2-i]))
    p_ans1 = max([gcd(gcd_left[i], gcd_right[N-i-3]) for i in range(N-2)])
    p_ans2 = gcd_left[N-2]
    p_ans3 = gcd_right[N-2]
    ans = max(p_ans1, p_ans2, p_ans3)
print(ans)

Measured memory_bytes: 24344
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), cout, ", ") << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, ostream &os = cout, string sep = " ")
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), os, ", ") << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, K);
    IN(ll, N);
    AIN(ll, A, N);
    A.push_back(A[0] + K);
    ll s = 0;
    ll x = 0;
    REP(i, N)
    {
        ll d = A[i + 1] - A[i];
        s += d;
        CH(max, x, d);
    }
    OUT(s - x);
}

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

int main(void){
    
    char s[101];
    int i,cnt=0;
    
    scanf("%s",s);
    
    for(i=0;i<strlen(s)/2;i++){
        if(s[i]!=s[strlen(s)-1-i]) cnt++;
    }
    
    printf("%d\n",cnt);
    
    return 0;
    
    
    
}


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

int n, arr[303030];
ll leftsum[303030], rightsum[303030];
ll ans = LLONG_MIN;
priority_queue <int, vector<int>, greater<int>> pq;
priority_queue <int> pq2;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 3 * n; i++)
        scanf("%d", &arr[i]);
    for (int i = 1; i <= n; i++)
    {
        leftsum[n] += arr[i];
        pq.push(arr[i]);
    }
    for (int i = n + 1; i <= 2 * n; i++)
    {
        int x = pq.top();
        if (arr[i] - x > 0)
        {
            leftsum[i] = leftsum[i - 1] + arr[i] - x;
            pq.pop();
            pq.push(arr[i]);
        }
        else
            leftsum[i] = leftsum[i - 1];
    }
    for (int i = 2*n+1; i <= 3*n; i++)
    {
        rightsum[2*n+1] += arr[i];
        pq2.push(arr[i]);
    }
    for (int i = 2 * n; i >= n + 1; i--)
    {
        int x = pq2.top();
        if (arr[i] - x < 0)
        {
            rightsum[i] = rightsum[i + 1] + arr[i] - x;
            pq2.pop();
            pq2.push(arr[i]);
        }
        else
            rightsum[i] = rightsum[i + 1];
    }
    for (int i = n; i <= 2 * n; i++)
        ans = max(ans, leftsum[i] - rightsum[i + 1]);
    printf("%lld", ans);
}


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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;


class Solver {
  public:
    bool solve() {
        const int NA = 'z' - 'a' + 1;
        string A; cin >> A;
        int N = A.size();
        rep(i, A.size()) A[i] -= 'a';
        int rec = 0;
        int cnt = 0;
        vector<int> contain(NA);
        vector<int> split;
       
        split.push_back(N - 1);
        for(int i = N - 1; i >= 0; i--) {
            char a = A[i];
            if(not contain[a]) {
                contain[a]++;
                cnt++;
                if(cnt == NA) {
                    fill(all(contain), 0);
                    rec++;
                    cnt = 0;
                    if(i > 0) split.push_back(i - 1);
                }
            }
        }
        string ans;
        if(cnt > 0) split.pop_back();       
        rep(i, NA) {
            if(not contain[i]) {
                ans.push_back('a' + i);
                break;
            }
        }        
        reverse(all(split));        
        rep(i, rec) {
            vector<int> c(NA), c_backup;
            int cnt = 0;
            int j;
            for(j = split[i]; cnt < NA; j--) {
                cnt += c[A[j]] == 0;                
                if(A[j] + 'a' == ans.back()) c_backup = c;
                c[A[j]] = 1;
            }
            c = c_backup;
            // if(cnt < NA - 1) c[A[j]] = 1;
            rep(k, NA) {
                if(not c[k]) {
                    ans.push_back(k + 'a');
                    break;
                }
            }            
        }
        cout << ans << endl;
        return 0;
    }
};

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


Measured memory_bytes: 720
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
  int n,k,x;
  vector<int> s;
  int start,end,ans=0,sum;
  
  while(1){
  
    cin>>n>>k;
    if(n==0 && k==0) break;
  
    for(int i=0;i<n;i++){
      cin>>x;
      s.push_back(x);
    }
    
    start=0;end=k;sum=0;
    for(int i=start;i<end;i++){
        sum+=s[i];
    }
    ans=max(ans,sum);
    
    while(end<n){
      sum+=s[end];
      sum-=s[start];
      ans=max(ans,sum);
      
      start++;end++;
    }
  
    printf("%d\n",ans);
    ans=0;sum=0;
    s.clear();
  }
  return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    int n = 7;
    int ans = 1;
    while(true) {
        if(n%k == 0)  {
            cout << ans << endl;
            return 0;
        }
        n*=10;
        n+=7;
        n%=k;
        ans++;
        if(ans >= k*2) break;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 3648
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    c = Counter(a)
    d = list(c.keys())
    x, y = min(d), max(d)
    ans = float("Inf")
    for i in range(x, y + 1):
        tmp = 0
        for k, v in c.items():
            tmp += (k - i) ** 2 * v
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

string s;

int main()
{
	cin>>s;
	int l=0;
	int bj=0;
	int ans=0;
	while(l<s.size())
	{
		if(bj==0)
		{
			l++;
			ans++;
			bj=1;
		}
		else
		{
			if(s[l]==s[l-1])
			{
				l=l+2;
				if(l>s.size())
				    break;
				ans++;
				bj=0;
			}
			else
			{
				l++;
				ans++;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }
const int MOD = 1000000007;
void solve(istream& cin, ostream& cout) {
	ll n,k;
	cin >> n >> k;
	ll ans = 0;
	ll maxi = 0;
	for(int j = 0; j < k-1; j++)
		maxi += n-j;
	for(int kk = k; kk <= n+1; kk++) {
		ll mini = kk*((ll)kk-1)/2;
		if(kk < n+1)
			maxi += n-kk+1;
		ans = (MOD+(ans+maxi-mini+1)%MOD)%MOD;
	//	cout << "kk= " << kk << ",mini=" <<mini << ",maxi=" <<maxi <<endl;
	}
	cout << ans << endl;
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<string> vs;
const long long INF = 1LL << 58;
const int INT_INF = 1 << 28;
const double PI = acos(-1.0);

int n, q, m;
vi a;

bool dfs(int i, int sum) {
  if (i == n)
    return sum == m;
  bool ret = false;
  if (dfs(i + 1, sum + a[i]))
    ret = true;
  if (dfs(i + 1, sum))
    ret = true;
  return ret;
}

int main() {
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];
  cin >> q;
  rep(i, q) {
    cin >> m;
    if (dfs(0, 0))
      cout << "yes" << endl;
    else
      cout << "no" << endl;
  }
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v),v.end()))
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define dbg(x);
#define dbgv(v);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
#ifdef ALEXPC
#define dbg(x); cout<<#x<<" = "<<x<<endl
#define dbgv(v); cout<<#v<<" = ["; trav(tv,v)cout<<"tv,";cout<<"]"<<endl
#endif

//const int N=100,M=N*N;
const ll MOD=1000*1000*1000+7;

const int N=1e6+6;


int main(){
    fastio;
    srng;
    int n;
    cin>>n;
    vector<pir> v;
    FOR(i,n){
        int a,b;
        cin>>a>>b;
        v.push_back({b,a});
    }
    sort(all(v));
    reverse(all(v));
    int tv=INT_MAX;
    FOR(i,n){
        tv=min(v[i].fr,tv);
        tv-=v[i].sc;
        if (tv<0){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}


Measured memory_bytes: 2420
import sys
input = sys.stdin.readline
n = int(input())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)


ans = [-1]*(n+1)
q = [1]
ans[1] = 0
while q:
    now = q.pop()
    for next in tree[now]:
        if ans[next] == -1:
            q.append(next)
            ans[next] = (ans[now]+1)%2

if ans.count(1) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 1:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            if onetwo_ind >= len(onetwo):
                ans[i] = three[three_ind]
                three_ind += 1
            else:
                ans[i] = onetwo[onetwo_ind]
                onetwo_ind += 1

elif ans.count(0) <= n//3:
    three = set([3*i+3 for i in range(n//3)])
    onetwo = set([i+1 for i in range(n)])
    onetwo = onetwo - three
    three = list(three)
    three.sort()
    onetwo = list(onetwo)
    onetwo.sort()
    three_ind = 0
    onetwo_ind = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = three[three_ind]
            three_ind += 1
        else:
            if onetwo_ind >= len(onetwo):
                ans[i] = three[three_ind]
                three_ind += 1
            else:
                ans[i] = onetwo[onetwo_ind]
                onetwo_ind += 1

else:
    zero = 0
    one = 0
    two = 0
    for i in range(1, n+1):
        if ans[i] == 0:
            ans[i] = zero*3+1
            zero += 1
        elif ans[i] == 1:
            ans[i] = one*3+2
            one += 1

    three = 0
    for i in range(1, n+1):
        if ans[i] > n:
            ans[i] = three*3+3
            three += 1

print(" ".join(map(str, ans[1:])))


Measured memory_bytes: 115660
package main

import (
	"fmt"
)

func main() {
  var s, t, u string
  var a, b int
  fmt.Scanf("%s %s", &s, &t)
  fmt.Scanf("%d %d", &a, &b)
  fmt.Scanf("%s", &u)

  ans := map[string]int{s:a, t:b}
  ans[u]--
  
  fmt.Printf("%d %d\n", ans[s], ans[t])
}

Measured memory_bytes: 1832
#include <bits/stdc++.h>
#define ll long long
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

int  main()
{
	 int A[4];
	 int a=0,b=0,c=0,d=0;
	 for(int i=0;i<4;i++)
	 {
	 	cin>>A[i];
	 	if(A[i]==1)
	 		{a++;	}
	 	if(A[i]==9)
	 		{	b++;}
	 	if(A[i]==7)
	 		{	c++;}
	 	if(A[i]==4)
	 		{	d++;}
	 }
	 
	 if(a==1&&b==1&&c==1&&d==1)
	 {
	 	cout<<"YES";
	 }
	 else
	 {
	 	cout<<"NO";
	 }
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,belong;
  SCC(){};
  SCC(int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
 
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
 
  void dfs(int v){
    used[v] = 1;
    for(int i=0;i<(int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
 
  void rdfs(int v,int k){
    used[v] = 1;
    belong[v] = k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++) {
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
 
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
 
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
    T.push_back(vector<int>());
    C.push_back(vector<int>());
    rdfs(vs[i],k++);
      }
    }
    return k;
  }
 
};
 
struct UnionFind{
  int n;
  vector<int> r,p;
  UnionFind(int n):n(n),r(n,1),p(n){iota(p.begin(),p.end(),0);}
  int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};
 
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n,m;
  while(cin>>n>>m,n){
    vector<int> x(m),y(m),c(m);
    int ans=0;
    UnionFind uf(n);
    SCC scc(n);
    for(int i=0;i<m;i++){
      cin>>x[i]>>y[i]>>c[i];
      if(c[i]<=0) ans+=c[i];
      else{
	scc.add_edge(x[i],y[i]);
	uf.unite(x[i],y[i]);
      }
    }
    if(uf.r[uf.find(0)]!=n){
      cout<<ans<<endl;
      continue;
    }
    scc.build();
    //cout<<ans<<endl;
    auto b=scc.belong;
    vector<int> v;
    int t=-1;
    for(int i=0;i<m;i++){
      if(c[i]<=0) continue;
      if(b[x[i]]==b[y[i]]){
	v.emplace_back(c[i]);
	continue;
      }
      if(t<0||c[i]<t) t=c[i];
    }
    sort(v.begin(),v.end());
    if(!v.empty()&&(t<0||v[0]+v[1]<t)) t=v[0]+v[1];
    cout<<ans+t<<endl;
  }
  return 0;
}

Measured memory_bytes: 3216