akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC086C
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());

            var points = new List<Point>();
            points.Add(new Point(0, 0, 0));
            for(int i = 0; i < count; i++)
            {
                var input = Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
                points.Add(new Point(input[0], input[1], input[2]));
            }

            bool result = true;
            for(int i = 1; i < points.Count(); i++)
            {
                if (!points[i].IsMovable(points[i - 1]))
                {
                    result = false;
                    break;
                }
            }

            Console.WriteLine(result ? "Yes": "No");
        }
    }

    class Point
    {
        public Point(int time, int x, int y)
        {
            Time = time;
            X = x;
            Y = y;
        }

        public int Time { get; }
        public int X { get; }
        public int Y { get; }

        public bool IsMovable(Point previous)
        {
            int dt = this.Time - previous.Time;
            int movingX = this.X - previous.X;
            int movingY = this.Y - previous.Y;

            int moving = movingX + movingY;

            if(dt < moving)
            {
                return false;
            }

            if (dt == moving)
            {
                return true;
            }

            if(dt > moving)
            {
                if ((dt - moving) % 2 == 0)
                {
                    return true;
                }
            }
            

            return false;
        }
    }
}


Measured memory_bytes: 20440
N,M = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(N)]

c =[[int(i) for i in input().split()] for j in range(M)]

n = 100000000000
n1 = 0
n2 = 0

for i in range(N):
    for j in range(M):
        n1 = abs(c[j][0] - a[i][0]) + abs(c[j][1] - a[i][1])
        if n1 < n:
            n = n1
            n2 = j
    n = 100000000000
    print(n2 + 1)


Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
		if (abs(a-c)<=d||(abs(a-b)<=d&&abs(b-c)<=d)){
            printf("Yes\n");
		}
	else{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 128
n, m, k = gets.split.map(&:to_i)
g = [0] * n

m.times do
	i, j = gets.split.map(&:to_i)
	i -= 1
	j -= 1
	g[i] |= (1 << j)
	g[j] |= (1 << i)
end

def del_trivial(g)
	trivial = 0
	loop do
		i = g.index {|x| x.to_s(2).count(?1) <= 1}
		break if !i
		if g[i].to_s(2).count(?1) == 0
			g.delete_at(i)
			g.map! do |x|
				l = (x >> i + 1)
				r = x & ((1 << i) - 1)
				(l << i) | r
			end
		else
			trivial += 1
			mask = (g[i] + (1 << i))
			(0..g.size-1).each do |j|
				if mask[j] == 1
					g[j] = 0
				else
					g[j] -= (g[j] & mask)
				end
			end
		end
	end

	return trivial
end

def f(graph, k)
	g = graph.dup
	i = (0..graph.size-1).max_by {|i| graph[i].to_s(2).count(?1) }
	return k >= 0 ? k : -Float::INFINITY if !i || graph[i] == 0
	return -Float::INFINITY if k <= 0

	(0..graph.size-1).each do |j|
		g[j] -= (1 << i) if g[j][i] == 1
	end
	g[i] = 0

	t = del_trivial(g)

	max = f(g, k-1-t)

	g = graph.dup
	d = g[i].to_s(2).count(?1)
	return max if d > k

	mask = g[i] | (1 << i)
	(0..graph.size-1).each do |j|
		if mask[j] == 1
			g[i] = 0
		else
			g[i] -= g[i] & mask
		end
	end

	t = del_trivial(g)
	ret = f(g, k-d-t)

	return ret > max ? ret : max
end

t = del_trivial(g)
c = f(g, k - t)
puts c >= 0 ? k - c : 'Impossible'

Measured memory_bytes: 60020
import java.util.*;
import java.util.stream.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int[] a = new int[n];
		for (int j = 0; j < n; j++) {
			a[j] = in.nextInt();
		}
		System.out.println((int)Math.ceil((n - 1) / (double)(k - 1)));
	}
}

Measured memory_bytes: 47952
fun main(arr:Array<String>) {
    val (n, y) = readLine()!!.split(" ").map { it.toInt() }
    getAns(n,y)
}

fun getAns(n:Int, y:Int) {
    if(n > y/1000 || n < y/10000) {
        println("-1 -1 -1")
        return
    }
    for(i in (0..y/10000).reversed()) {
        var remain = y - (i*10000)
        var current = remain / 1000
        var c5000 = 0
        while (current + c5000 + i >= n + 4 && current >= 5) {
            c5000++
            current -= 5
        }
        if(current + c5000 + i == n) {
            println("%d %d %d".format(i, c5000, current))
            return
        }
    }
    println("-1 -1 -1")
}

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

using namespace std;

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 (a>b) { a=b; return 1; } return 0; }

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

	int h1, h2, m1, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;

	int ans = h2 * 60 + m2 - k - (h1 * 60 + m1);
	cout << ans << endl;
}


Measured memory_bytes: 3656
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define DEBUG(X) cerr<<__LINE__<<" "<<#X<<": "<<X<<endl;
#define sci(x) int x;scanf("%d",&x);
#define scii(x, y) int x,y;scanf("%d%d",&x,&y);
int main() {
  scii(A,B) sci(C)
  printf(A<=C&&C<=B?"Yes\n":"No\n");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ll n,c=0;
    cin>>n;
    if(n>=500)
    {
        c+=(n/500)*1000;
        n=n%500;
    }

    if(n>=5)
    {
        c+=(n/5)*5;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
/* Author rumoisen */
/* created 2018/10/20 */

#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <iostream>

using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7
#define pb push_back

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

void no(){cout<<"No"<<endl;exit(0);}
void yes(){cout<<"Yes"<<endl;exit(0);}
void No(){cout<<"NO"<<endl;exit(0);}
void Yes(){cout<<"YES"<<endl;exit(0);}

using namespace std;

int main(void)
{
    int a,b,k;
    cin>>a>>b>>k;
    for(int i=0;i<k;i++){
        if(i%2==0){
        if(a%2==1){
            a-=1;
        }
        b+=a/2,a-=a/2;
        }
        if(i%2==1){
            if(b%2==1){
                b-=1;
            }
            a+=b/2;
            b-=b/2;
        }
    }
    cout<<a<<' '<<b<<endl;
    return 0;
}

Measured memory_bytes: 256
#pragma once
#include<stdio.h>

long dan,amari;
long result=0;
bool find = false;
long tate=1;
long yoko=2;
long start[2]={};
long a[2]={};
long aida=0;

int main(){

	scanf("%d",&dan);
	scanf("%d",&amari);
	dan--;

	if(dan>=3){
		while(find == false){
			if((tate*7+yoko)*9 % 11 == amari){
				start[0]=tate;
				start[1]=yoko;
				find=true;
			}
			else{
				yoko++;
				if(yoko%7 == 0 || yoko%7==1){
					tate++;
					yoko=2;
					if(tate>=dan){
						break;
					}
				}

			}


		}

		for(int i=1;i<=7;i++){
			if((start[1] + i*4)%7 == 0){
				a[0]=i;
			}
			if((start[1] + i*4)%7 == 1){
				a[1]=i;
			}
		}


		if(find ==true){
			aida = dan*7-1-(start[0]*7+start[1]);
			result = (aida/77)*5+1;
			result+= (aida%77)/11;

			if(aida%77>=11*a[0]){
				result--;
			}

			if(aida%77>=11*a[1]){
				result--;
			}
		}

	}

	printf("%ld\n",result);

return 0;
}



Measured memory_bytes: 128
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int StringToInt(const string& str){
  int n;
  istringstream iss(str);
  iss >> n;
  return n;
}

vector<int> StringToVectorInt(string& str){
  vector<int> data;
  string::iterator i, j;
  i = str.begin();
  while(1){
    j = find(i, str.end(), ',');
    const string str_(i, j);
    data.push_back(StringToInt(str_));
    if(j == str.end()) return data;
    i = j+1;
  }
}

int GetMaxValue(vector< vector<int> > data){
  for(int i=1; i<data.size(); ++i){
    for(int j=0; j<data[i].size(); ++j){
      if(i <= data.size()/2){
	if(j == 0)
	  data[i][j] += data[i-1][j];
	else if(j == data[i].size()-1)
	  data[i][j] += data[i-1][j-1];
	else
	  data[i][j] += max(data[i-1][j-1], data[i-1][j]);
      }else{
	data[i][j] += max(data[i-1][j], data[i-1][j+1]);
      }
    }
  }
  return data[data.size()-1][0];
}

int main(){
  string str;
  vector< vector<int> > data;

  while(cin >> str)
    data.push_back(StringToVectorInt(str));

  cout << GetMaxValue(data) << endl;
  return 0;
}

Measured memory_bytes: 1272
import Control.Monad
import Control.Applicative
import Data.List
import Data.Array
strToInt s = (read :: String -> Int) s

main = do
    [n,m] <- (map read . words) <$> getLine
    
    let ans = ((1900 * m) + (100 * (n-m)) ) * ([1,2,4,8,16,32] !! m)
    print ans

Measured memory_bytes: 508
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	static class TaskX {

		int[][] sum;
		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int n = in.nextInt(), k = in.nextInt();
			int[][] mat = new int[4*k+1][4*k+1];
			for (int i = 0; i < n; i++) {
				int x = in.nextInt();
				int y = in.nextInt();
				char c = in.nextString().charAt(0);
				if (c == 'B') {
					x += k;
				}
				mat[x%(2*k)][y%(2*k)]++;
			}

			for (int i = 0; i < 4*k; i++) {
				for (int j = 0; j < 4*k; j++) {
					mat[i][j] = mat[i%(2*k)][j%(2*k)];
				}
			}

			sum = new int[4*k+1][4*k+1];

			for (int i = 0; i <= 4*k; i++) {
				for (int j = 0; j <= 4*k; j++) {
					sum[i][j] = mat[i][j];
					if (j-1 >= 0) sum[i][j] += sum[i][j-1];
					if (i-1 >= 0) sum[i][j] += sum[i-1][j];
					if (i-1 >= 0 && j-1 >= 0) sum[i][j] -= sum[i-1][j-1];
				}
			}

			long ans = 0;
			for (int i = 0; i < 2*k; i++) {
				for (int j = 0; j < 2*k; j++) {
					ans = Math.max(ans, calcSum(i, j, i+k-1, j+k-1) + calcSum(i+k, j+k, i+2*k-1, j+2*k-1));
				}
			}

			out.println(ans);
		}

		int calcSum(int x1, int y1, int x2, int y2) {
			int res = sum[x2][y2];
			if (x1 > 0) res -= sum[x1-1][y2];
			if (y1 > 0) res -= sum[x2][y1-1];
			if (x1 > 0 && y1 > 0) res += sum[x1-1][y1-1];
			return res;
		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}


Measured memory_bytes: 203640
from collections import Counter
def get_par(x, par_lst):
  if x == par_lst[x]:
    return x
  ret = get_par(par_lst[x], par_lst)
  par_lst[x] = ret
  return ret

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    par_lst = [i for i in range(n)]
    counter = Counter()
    flag = False
    if m == 0:
      print("yes")
      continue
    for _ in range(m):
      u, v = map(int, input().split())
      u -= 1
      v -= 1
      counter[u] += 1
      counter[v] += 1
      pu, pv = get_par(u, par_lst), get_par(v, par_lst)
      if pu == pv:
        flag = True
      else:
        par_lst[pu] = pv
    
    if counter.most_common()[0][1] > 2:
      flag = True
    if flag:
      print("no")
    else:
      print("yes")
main()


Measured memory_bytes: 13820
n = int(input())
s, p = [], []
for i in range(n):
  inp = input().split()
  s.append(inp[0])
  p.append(int(inp[1]))

ans_list = list(i for i in range(1, n + 1))
for i in range(n):
  index = i
  for j in range(i, n):
    if s[index] > s[j] or (s[index] == s[j] and p[index] < p[j]):
      index = j
  s[i], s[index] = s[index], s[i]
  p[i], p[index] = p[index], p[i]
  ans_list[i], ans_list[index] = ans_list[index], ans_list[i]

for i in ans_list:
  print(i)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
#define toupper(S) transform(S.begin(),S.end(),S.begin(),toupper)
#define tolower(S) transform(S.begin(),S.end(),S.begin(),tolower)
const lint MOD = pow(10, 9) + 7;


int main() {
	int N;
	cin >> N;
	vector<int>X(N);
	rep(i, N) {
		cin >> X[i];
	}
	int ans = INT_MAX;
	int sum = 0;
	for (int i = 1; i <= 100; i++) {
		rep(j, N) {
			sum += (X[j] - i) * (X[j] - i);
		}
		ans = min(ans, sum);
		sum = 0;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct UnionFind{
	vi data;
	UnionFind(int size):data(size,-1){}
	int Find(int n){
		return data[n]<0?n:(data[n]=Find(data[n]));
	}
	void Unite(int a,int b){
		int ra=Find(a),rb=Find(b);
		if(ra!=rb){
			if(-data[ra]<-data[rb])
				swap(ra,rb);
			data[ra]+=data[rb];
			data[rb]=ra;
		}
	}
	int Size(int n){
		return -data[Find(n)];
	}
};

int h,w;
char grid[12][13];
int ice[12][12],vis[12][12],lim[12*12];
int gi,gj;
int res;

inline void dfs(int i,int j,int step)
{
	if(grid[i][j]=='X' && lim[ice[i][j]]==0) return;
	if(grid[i][j]=='G') res=min(res,step);
	if(step+abs(gi-i)+abs(gj-j)>=res) return;
	
	vis[i][j]=true;
	if(grid[i][j]=='X') lim[ice[i][j]]--;
	rep(k,4){
		int ni=i+"\xff\x1\0\0"[k],nj=j+"\0\0\xff\x1"[k];
		if(ni<0 || h<=ni || nj<0 || w<=nj || grid[ni][nj]=='#' || vis[ni][nj]) continue;
		dfs(ni,nj,step+1);
	}
	if(grid[i][j]=='X') lim[ice[i][j]]++;
	vis[i][j]=false;
}

int main()
{
	for(;cin>>w>>h,w|h;){
		rep(i,h) cin>>grid[i];
		
		UnionFind uf(h*w);
		rep(i,h) rep(j,w){
			if(grid[i][j]=='X'){
				if(i+1<h && grid[i+1][j]=='X')
					uf.Unite(i*w+j,(i+1)*w+j);
				if(j+1<w && grid[i][j+1]=='X')
					uf.Unite(i*w+j,i*w+(j+1));
			}
		}
		map<int,int> f;
		memset(ice,-1,sizeof(ice));
		rep(i,h) rep(j,w) if(grid[i][j]=='X'){
			if(!f.count(uf.Find(i*w+j)))
				f.insert(mp(uf.Find(i*w+j),f.size()));
			ice[i][j]=f[uf.Find(i*w+j)];
		}
		vi cnt(f.size());
		rep(i,h) rep(j,w) if(grid[i][j]=='X')
			cnt[ice[i][j]]++;
		rep(i,cnt.size()) lim[i]=cnt[i]/2;
		
		res=INFTY;
		rep(i,h) rep(j,w) if(grid[i][j]=='G')
			gi=i,gj=j;
		rep(i,h) rep(j,w) if(grid[i][j]=='S')
			dfs(i,j,0);
		cout<<res<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1208
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var a = ReadInts();

            var ans = 0;
            for (int i = 0; i < N; i++)
            {
                if ((i + 1) % 2 != 0)
                {
                    if (a[i] % 2 != 0)
                    {
                        ans++;
                    }
                }
            }
            WriteLine(ans);
        }

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


Measured memory_bytes: 27508
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll x, y;std::cin >> x >> y;
  for(int i=0;i<=x;i++){
    ll l = y - 2*i;
    ll r = x - i;
    if(l<0) continue;
    if(l==4*r){
      std::cout << "Yes" << '\n';
      return 0;
    }
  }
  std::cout << "No" << '\n';
  return 0;
}


Measured memory_bytes: 3108
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;



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

	string S; cin >> S;
	int N = S.size();
	vector<VI>dp(N + 1, VI(2, 0));


	dp[0][0] = 2;
	dp[0][1] = 1;

	FOR(i, 1, N) {
		if (S[i] == '0') {
			dp[i][0] = dp[i - 1][0];
			dp[i][1] = (dp[i - 1][1] * 3) % mod;
		}
		else {
			dp[i][0] = (dp[i - 1][0] * 2) % mod;
			dp[i][1] = (dp[i - 1][1] * 3 + dp[i - 1][0]) % mod;
		}
	}





	cout << (dp[N - 1][0] + dp[N - 1][1]) % mod << endl;

	return 0;
}



Measured memory_bytes: 5840
package main

import "fmt"

func main() {
	var l, r, d int
	fmt.Scanf("%d", &l)
	fmt.Scanf("%d", &r)
	fmt.Scanf("%d", &d)

	var ans int
	for i := l; i <= r; i++ {
		if i%d == 0 {
			ans++
		}
	}

	fmt.Println(ans)
}


Measured memory_bytes: 1832
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
#define rep1(i,n) for (ll i=1; i<=(n); ++i)
typedef long long ll;
bool debug=false;
string yes = "Yes";
string no = "No";
const ll mod = 998244353;

int main(){
  ll k; cin >> k;
  string s; cin >> s;
  string ans = s;
  if(s.size()>k){
    ans = ans.substr(0,k)+"...";
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3628
N,M= map(int,input().split())

sc = [list(map(int,input().split())) for i in range(M)]

ans = [0]*N
if N != 1:
    ans[0] = 1

pre_s = []

check = {}
for s,c in sc:
    if s in check:
        if c != check[s]:
            print(-1)
            exit()
    else:
        check[s] = c
    ans[s-1] = c

ans = int("".join(map(str,ans)))

if len(str(ans)) != N:
    print(-1)
    exit()

print(ans)


Measured memory_bytes: 38384
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,D,Q,K,R,W,H,P,L,G;
ll ans;
string S,T;
ll y[101010];
ll a[101010];
ll k[101010];
ll b[101010];
ll d[101010];
ll t[101010];
ll p[101010];
ll n[101010];
ll l[101010];
ll r[101010];
ll v[101010];
ll s[101010];
ll x[101010];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
struct Edge{
	ll to,cost;
	 Edge(ll to, ll cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<ll> size;
    UnionFind(ll N) : par(N),size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
		for(ll i = 0; i < N; i++) size[i] = 1;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
	ll GetSize(ll x){
		return size[root(x)];
	}

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry]+=size[rx];

    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};

int main() {
    cin>>A>>B>>C>>D;
    A--;
    ll Anum = A - (A/C + A/D - A/lcm(C,D) );
    ll Bnum = B - (B/C + B/D - B/lcm(C,D) );
    cout<<Bnum-Anum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,a[10001],ans=0;
    cin>>n;
    for(int i=0;i<2*n;i++){
        cin>>a[i];
    }
    sort(a,a+2*n);
    for(int i=0;i<2*n;i+=2){
        ans+=a[i];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader reader = new BufferedReader(isr);
		Main app = new Main();
		String str, s[];
		
		int a, b, c, max;
		while(!(str = reader.readLine()).equals("0 0 0")){
			s = str.split(" ");
			a = Integer.valueOf(s[0]);
			b = Integer.valueOf(s[1]);
			c = Integer.valueOf(s[2]);
			
			max = -1;
			for(int i = 1; i < c; i++){
				for(int j = 1; j < c; j++){
					if(app.set(i, a) + app.set(j, a) == c){
						max = Math.max(app.set(i, b) + app.set(j, b), max);
					}
				}
			}
			System.out.println(max);
		}
	}
	
	public int set(int p, int x){
		return p * (100 + x) / 100;
	}
}

Measured memory_bytes: 25332
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main()
{
    string s;
    cin >> s;
    int len = s.size();
    int cnt = 0;
    rep(i, 0, len) {
        if (s[i] == 'B') cnt ++;
    }
    ll ans = 0;
    int r = len - cnt;
    rep(i, 0, len) {
        if (s[i] == 'B') {
            ans += r - i;
            r ++;
        }
    }

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


Measured memory_bytes: 640
#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(10 ** 5 + 1)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[s - 1][c - 1] += 1
    table[t - 1][c - 1] -= 1

imos = [0] * (10 ** 5 + 1)
for i in range(10 ** 5 + 1):
    for j in range(C):
        if table[i][j] == 1:
            imos[i] += 1
        if table[i][j] == -1:
            imos[i + 1] -= 1

ans = 0
for i in range(1, 10 ** 5 + 1):
    imos[i] += imos[i - 1]
    ans = max(ans, imos[i])

print(ans)


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

using namespace std;

int main()
{
  int H, W;
  cin >> H >> W;
  vector<string> s(H);

  for(int i = 0;
      i < H;
      ++i)
    {
      cin >> s[i];
    }
  int dp[H][W];
  for(int i = 0;
      i < H;
      ++i)
    {
      for(int j = 0;
          j < W;
          ++j)
        {
          dp[i][j] = 0;
        }
    }
  int st = 0;

  for(int i = 0;
      i < H;
      ++i)
    {
      for(int j = 0;
          j < W;
          ++j)
        {
          if(s[i][j] == '#' || j == W - 1)
            {
              if(s[i][j] != '#' && j == W - 1)
                {
                  ++j;
                }
              for(int k = st;
                  k < j;
                  ++k)
                {
                  dp[i][k] = (j - st);
                }
              st = j + 1;
            }
        }
      st = 0;
    }

  st = 0;
  int ans = 0;
  for (int i = 0;
       i < W;
       ++i)
    {
      for(int j = 0;
          j < H;
          ++j)
        {
          if(s[j][i] == '#' || j == H - 1)
            {
              if(s[j][i] != '#' && j == H - 1)
                {
                  ++j;
                }
              for(int k = st;
                  k < j;
                  ++k)
                {
                  dp[k][i] += (j - st) - 1;
                  ans = max(ans,dp[k][i]);
                }
              st = j + 1;
            }
        }
      st = 0;
    }

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


Measured memory_bytes: 19968
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#define abs(a) ((a) < 0 ? - (a) : (a))
using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  
  if (abs(a - b) % 2 == 1)
    cout << "IMPOSSIBLE" << endl;
  else
    cout << (a + b) / 2 << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 1005;

int a[10][N];
int b[10];
int d[10];
int main() {
    int n, m, K;
    cin >> n >> m >> K;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            scanf("%1d", &a[i][j]);
    }
    int ans = n + m;
    for (int s = 0; s < 1 << n - 1; s++) {
        int now = __builtin_popcount(s);
        int tot = 0;
        d[0] = tot;
        for (int i = 0; i < n - 1; i++) {
            if (s >> i & 1) {
                ++tot;
            }
            d[i + 1] = tot;
        }
        memset(b, 0, sizeof b);
        for (int j = 0; j < m; j++) {
            int ok = 1;
            for (int i = 0; i < n; i++) {
                b[d[i]] += a[i][j];
                if (b[d[i]] > K) ok = 0;
            }
            if (ok == 0) {
                memset(b, 0, sizeof b);
                now++;
                for (int i = 0; i < n; i++) {
                    b[d[i]] += a[i][j];
                    if (b[d[i]] > K) goto M1;
                }
            }
        }
        ans = min(ans, now);
    M1:;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
// Diagonal String

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){
	char c[3][3];

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < 3; ++j)
			cin >> c[i][j];

	for (int i = 0; i < 3; ++i)
		cout << c[i][i];

	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<map>
#include<iostream>
#include<deque>
#include<algorithm>
#include<string>
#include<cctype>
#include<iomanip>
#include<vector>
#include<queue>
 
using namespace std;
#define REP(i,b,e) for(ll i=(ll)b;i<(ll)e;i++)
#define rep0(i,n) REP(i,0ll,n)
#define rep1(i,n) REP(i,1ll,n+1)
 
#define shosu setprecision(10)
 
typedef long long ll;
typedef pair<int,int> P;
ll longinf=1ll<<60;
int inf=1<<29;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int hoge[30][100001];
int used[30][100001];
int anss[100001];
int main (){
      int N,C;
      cin>>N>>C;
      int s[N],t[N],c[N];
      rep0(i,N){
            cin>>s[i]>>t[i]>>c[i];
            --c[i];
      }
      rep0(ch,C){
            rep0(i,N){
                  if(c[i]==ch){
                        hoge[ch][s[i]-1]++;
                        hoge[ch][t[i]]--;
                  }
            }
      }
      rep0(ch,C){
            rep0(t,100001){
                  if(t==0) used[ch][t]=hoge[ch][t];
                  else used[ch][t]=used[ch][t-1]+hoge[ch][t];
            }
      }
      rep0(ch,C)rep0(t,100001){
            if(used[ch][t]>0) used[ch][t]=1;
      }
      rep0(t,100001)rep0(ch,C){
            anss[t]+=used[ch][t];
      }
      int ans=0;
      rep0(t,100001){
            ans=max(ans,anss[t]);
      }
      cout<<ans<<endl;

      
      return 0;
}


Measured memory_bytes: 25216
//file_name:ABC73_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    int n;
    scanf("%d",&n);
    ll ans = 0;
    rep(i,n){
        int l,r;
        cin >> l >> r;
        ans += r-l+1;
    }
    cout << ans << endl;
    return 0;
}



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

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

const int maxn = 1e5 + 10;
vector<int> adj[maxn]; 
int p[maxn], n, k, d[maxn];

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	} scanf("%d", &k);
	memset(p, -1, sizeof p);
	
	priority_queue<ii, vector<ii>, greater<ii> > q;
	for(int i = 0; i < k; i++) {
		int u; scanf("%d", &u);
		scanf("%d", &p[u]);
		q.push({p[u], u});
	} 
	while(!q.empty()) {
		ii x = q.top(); q.pop(); 
		int val = x.first, u = x.second; 
		for(int v : adj[u]) {
			if(p[v] == -1) {
				p[v] = val + 1;
				q.push({p[v], v});
			}
			else if(abs(p[v] - p[u]) != 1) {
				puts("No"); return 0;
			}
		}
	}
	puts("Yes");
	for(int i = 1; i <= n; i++) {
		printf("%d\n", p[i]);
	}

}

Measured memory_bytes: 7924
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 185;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];
    int f[N][N][N + 1] = {};
    for (int c = m - 1; c >= 0; --c) {
        for (int r1 = 0; r1 < n; ) {
            int r2 = r1;
            while (r2 < n && s[r1][c] == s[r2][c])
                ++r2;
            for (int i = r1; i < r2; ++i)
                for (int j = i; j < r2; ++j)
                    f[i][j][c] = 1 + (c < m - 1 && s[i][c] == s[i][c + 1] ? f[i][j][c + 1] : 0);
            r1 = r2;
        }
    }
    int ans = 0;
    while (f[0][n - 1][0] != m) {
        ++ans;
        for (int c = 0; c < m; ++c) {
            for (int r1 = 0; r1 < n; ++r1) {
                for (int r2 = n - 1, i = n - 1; r2 >= r1; --r2) {
                    f[r1][r2][c] += f[r1][r2][c + f[r1][r2][c]];
                    if (r1 == r2)
                        continue;
                    if (i < r2)
                        ++i;
                    while (i > r1 + 1 && f[r1][i - 1][c] < f[i][r2][c]) {
                        f[r1][r2][c] = max(f[r1][r2][c], min(f[r1][i - 1][c], f[i][r2][c]));
                        --i;
                    }
                    f[r1][r2][c] = max(f[r1][r2][c], min(f[r1][i - 1][c], f[i][r2][c]));
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 25344
def hotels(lodging_all, lodging_first, price_first, price_second)
  if lodging_all >= lodging_first
    lodging_second = lodging_all - lodging_first
    price_all = lodging_first * price_first + lodging_second * price_second
  else
    price_all = lodging_all * price_first
  end
  p price_all
end

lodging_all = gets.chomp.to_i
lodging_first = gets.chomp.to_i
price_first = gets.chomp.to_i
price_second = gets.chomp.to_i
hotels(lodging_all, lodging_first, price_first, price_second)

Measured memory_bytes: 1788
N, M = map(int, input().split())

dict_path = {}
path = []

for i in range(M):
    a, b = input().split()
    path.append((a, b))
    path.append((b, a))

for i in range(1, N+1):
    tmp = []
    for j in path:
        a, b = j
        if a == str(i):
            tmp.append(b)
    dict_path[str(i)] = tmp

stack = ['1']
root = ['1']

ans = 0
while stack:
    path = stack.pop(-1)
    now = path[-1]
    for i in dict_path[now]:
        tmp = path
        if i not in path:
            tmp += i
            if tmp not in root:
                stack.append(tmp)
                root.append(tmp)
                if len(tmp) == N:
                    ans += 1

print(ans)


Measured memory_bytes: 3956
l = []
3.times do
  l << gets.split(' ').map(&:to_i)
end

n = gets.to_i
b = []
n.times do
  b = gets.to_i
  l.each_with_index do |v,i|
    3.times do |ii|
      if v[ii] == b
        l[i][ii] = 'x'
        next
      end
    end
  end
end

if l[0].count('x') == 3 or l[1].count('x') == 3 or l[2].count('x') == 3 \
   or (l[0][0] == 'x' and l[1][1] == 'x' and l[2][2] == 'x') \
   or (l[0][2] == 'x' and l[1][1] == 'x' and l[0][2] == 'x') \
   or (l[0][0] == 'x' and l[1][0] == 'x' and l[2][0] == 'x') \
   or (l[0][1] == 'x' and l[1][1] == 'x' and l[2][1] == 'x') \
   or (l[0][2] == 'x' and l[1][2] == 'x' and l[2][2] == 'x')
  puts 'Yes'
else
  puts 'No'
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define PI 3.1415926535897932
#define MOD 1000000007;
using namespace std;
long long GCD(long long A,long long B){
  if(B==0){
    return A;
  }
  else{
    return GCD(B,A%B);
  }
}
long long LCM(long long A,long long B){
  long long g=GCD(A,B);
  return A/g*B;
}
long long num_order(long long X){
  long long ans=0;
  while(true){
    if(X==0){
      break;
    }
    else{
      X/=10;
      ans++;
    }
  }
  return ans;
}
int main() {
  
  vector<int> num(3);
  cin>>num[0]>>num[1]>>num[2];
  sort(num.begin(),num.end());
  
  int ans=0;
  
  
  while(abs(num[0]-num[2])>1){
    num[0]+=2;
    ans++;
  }
  while(abs(num[1]-num[2])>1){
    num[1]+=2;
    ans++;
  }
  sort(num.begin(),num.end());
  
  if(num[0]<num[1]&&num[1]<num[2]){
    ans+=3;
  }
  else if(num[0]==num[1]&&num[1]<num[2]){
    ans++;
  }
  else if(num[0]<num[1]&&num[1]==num[2]){
    ans+=2;
  }
  
  
  cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll mod = 1000000007;

const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


void eratosthenesbool(vector<bool> &prime, ll n) {
  for (int i = 0; i < n; i++) prime[i] = 1;
  prime[0] = prime[1] = 0;
  for (int i = 0; i < n; i++) {
    if (prime[i]) {
      for (int j = i + i; j < n; j += i) {
        prime[j] = 0;
      }
    }
  }
}



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


  vector<ll> x(n);
  vector<ll> y(m);

  cin >> x;
  cin >> y;




  ll xsumbase = 0;
  for (ll i = 1; i < n; i++) {
    xsumbase += x[i] - x[0];
  }

  ll xsum = xsumbase;
  ll tmpxsum = xsumbase;
  for (ll i = 1; i < n ; i++) {
    tmpxsum -= ( x[i] - x[i-1] ) * (n - i );
    xsum += tmpxsum;
    cerr << tmpxsum << endl;
  }

  cerr << xsumbase << " " << xsum << endl;

  xsum %= mod;
  ll ans = 0;

  //////////////////////////////////////////////////

  ll ysumbase = 0;
  for (ll i = 1; i < m; i++) {
    ysumbase += y[i] - y[0];
  }




  ll ysum = ysumbase;
  ll tmpysum = ysumbase;
  for (ll i = 1; i < m - 1; i++) {
    tmpysum -= ( y[i] - y[i-1] ) * (m - i );
    ysum += tmpysum;
    cerr << tmpysum << endl;
  }

  cerr << ysumbase <<" " << ysum <<endl;



  ysum %= mod;


  ans = xsum*ysum;
  ans%=mod;


  cout << ans << endl;
}




















Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;




int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
	
	int i,n;
	ll ans=0;
	cin>>n;
	int v[n],c[n];
	rep(i,n)cin>>v[i];
	rep(i,n)cin>>c[i];
	rep(i,n){
		if(v[i]-c[i]>0)ans+=v[i]-c[i];
	}
	cout<<ans<<endl;
	
//////////////////////////////////////////////////////
	return 0;
}








Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
    ll N, K;
    cin >> N >> K;
    if(N%K==0){
        cout << 0 << endl;
    } else {
        cout << min(N%K, K-(N%K)) << endl;
    }

}

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

int main(){
	int n ; cin >> n ;
	int mn = 10000000 ;
	int mx = -1000000 ;
	for(int i=0;i<n;i++){
		int a ; cin >> a ;
		mn = min(mn,a) ;
		mx = max(mx,a) ;
	}
	cout << mx-mn << endl ;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var a, b, c, d int
	fmt.Scanf("%d %d %d %d", &a, &b, &c, &d)

	g := gcd(c, d)

	lcm := c * d / g

	/* 1~bでc,dで割り切れない数の個数 */
	bNum := b - canDivCnt(b, c, d, lcm)

	/* 1~(a-1)でc,dで割り切れない数の個数 */
	aNum := (a - 1) - canDivCnt(a-1, c, d, lcm)

	/* a~bでc,dで割り切れない数の個数 */
	ans := bNum - aNum

	fmt.Printf("%d\n", ans)

}

/* 1~nでdiv1かdiv2で割りきれる数の個数を返す */
func canDivCnt(n int, div1 int, div2 int, lcm int) int {
	return (n / div1) + (n / div2) - n/lcm
}

func gcd(a int, b int) int {
	if a < b {
		tmp := b
		b = a
		a = tmp
	}
	tmp := a % b
	if tmp == 0 {
		return b
	} else {
		return gcd(b, tmp)
	}
}


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

int h[101][101];

void check1(int xx, int yy, int hh)
{
  for (auto y = 0; y <= 100; y++) {
    for (auto x = 0; x <= 100; x++) {
      if (h[y][x] < 0) continue;
      int t = hh + abs(x - xx) + abs(y - yy);
      if (h[y][x] == 0) {
	h[y][x] = t;
	continue;
      }
      if (h[y][x] != t) {
	h[y][x] = -1;
	continue;
      }
    }
  }
}

void check2(int xx, int yy)
{
  for (auto y = 0; y <= 100; y++) {
    for (auto x = 0; x <= 100; x++) {
      if (h[y][x] < 0) continue;
      int t = abs(x - xx) + abs(y - yy);
      if (t - h[y][x] < 0) {
	h[y][x] = -1;
	continue;
      }
    }
  }
}

void print_ans()
{
  for (auto y = 0; y <= 100; y++) {
    for (auto x = 0; x <= 100; x++) {
      if (h[y][x] > 0) {
	cout << x << " " << y << " " << h[y][x] << endl;
      }
    }
  }
}

int main()
{
  int n;
  cin >> n;
  int px[n], py[n], ph[n];

  for (auto i = 0; i < n; i++) {
    cin >> px[i] >> py[i] >> ph[i];
  }
  for (auto i = 0; i < n; i++) {
    if (ph[i] > 0) check1(px[i], py[i], ph[i]);
  }
  for (auto i = 0; i < n; i++) {
    if (ph[i] == 0) check2(px[i], py[i]);
  }
  print_ans();
}


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

public class Main {

    static long mod = (long) (1e9 + 7);

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        int ans = 0;
        for (int k = n - 1; k >= 0; k--) {
            int i = 0;
            int j = k - 1;
            int large = a[k];
            while (i < j) {
                int sum = a[i] + a[j];
                if (sum > large) {
                    ans = (ans + (j - i));
                    j--;
                } else {
                    i++;
                }
            }
        }
        out.println(ans);
        out.close();
    }

    static long[][] powMat(long[][] a, long pow) {
        if (pow == 1) {
            return a;
        } else {
            if (pow % 2 == 0) {
                return powMat(mul(a, a), pow / 2);
            } else {
                return mul(a, powMat(mul(a, a), pow / 2));
            }
        }
    }

    static long[][] mul(long[][] a, long[][] b) {
        int n = a.length;
        long[][] c = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    c[i][k] = (c[i][k] + (a[i][j] * b[j][k]) % mod) % mod;
                }
            }
        }
        return c;
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main(){
	int n,K;cin>>n>>K;
	if(K==1){
		puts("0");return 0;
	}
	cout<<(n-K)<<endl;
}

Measured memory_bytes: 256