akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll LL_MAX=LLONG_MAX;

struct In{
    template<typename T>
    operator T(){
        T x;
        cin >> x;
        return x;
    }
};
In in;

template <typename T,typename U>
void forin(T* x,U n){
    for (U i=0;i<n;i++) cin >> x[i];
}

template <typename T>
int div1(T x) {
    return x%1000000007;
}

template <typename T>
void out(T x){
    cout << x << endl;
}

template <typename T>
T gcd(T x,T y){
    if (y == 0) return x;
    return gcd(y,x%y);
}

template <typename T>
T lcm(T x,T y){
    return x*y/gcd(x,y);
}

int main(){
    int h=in,a=in;
    out((h+a-1)/a);
}

Measured memory_bytes: 256
package main

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

func main() {
	N := nextInt()
	var tasks pairs = make([]pair, N)

	for i := 0; i < N; i++ {
		tasks[i] = pair{nextInt64(), nextInt64()}
	}

	sort.Sort(tasks)

	t := int64(0)

	for i := 0; i < N; i++ {
		t += tasks[i].left

		if t > tasks[i].right {
			fmt.Println("No")
			return
		}
	}

	fmt.Println("Yes")
}

type pair struct {
	left  int64
	right int64
}
type pairs []pair

func (p pairs) Len() int {
	return len(p)
}
func (p pairs) Less(i, j int) bool {
	return p[i].right < p[j].right || p[i].right == p[j].right && p[i].left < p[j].left
}
func (p pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)

	return i
}


Measured memory_bytes: 8192
#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() {
  string S, T;
  cin >> S >> T;
  int ans = 0;
  rep(i,S.size()) {
    if (S[i] != T[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3892
#include <bits/stdc++.h>
#define X real()
#define Y imag()
using namespace std;
typedef complex <double> point;
typedef pair <double,int> P;

double cross(point a,point b){return a.X*b.Y-a.Y*b.X;}
double dot(point a,point b){return a.X*b.X+a.Y*b.Y;}

int ccw(point a,point b,point c){
  point d = b-a;
  point e = c-a;
  if(cross(d,e)>0) return 1;//"COUNTER_CLOCKWISE"
  if(cross(d,e)<0) return -1;//"CLOCKWISE"
  if(dot(d,e)<0) return 2;//"ONLINE_BACK"
  if(abs(d)<abs(e)) return -2;//"ONLINE_FRONT"
  return 0;//"ON_SEGMENT"
}

bool intersection(point a,point b,point c,point d){
  return (ccw(a,b,c)*ccw(a,b,d)<=0&&ccw(c,d,a)*ccw(c,d,b)<=0);
}

point CrossPoint(point a,point b,point c,point d){
  point base=d-c;
  double d1=abs(cross(base,(a-c)));
  double d2=abs(cross(base,(b-c)));
  double t=d1/(d1+d2);
  return (b-a)*t+a;
}

int main(){
  int q;
  cin>>q;
  while(q--){
    int sx,sy,gx,gy,n,o[101],l[101];
    cin>>sx>>sy>>gx>>gy;
    cin>>n;
    
    P D[101];
    for(int i=0,a,b,c,d;i<n;i++){
      cin>>a>>b>>c>>d>>o[i]>>l[i];
      point S=point(sx,sy),G=point(gx,gy),S2=point(a,b),G2=point(c,d);
      if(!intersection(S,G,S2,G2))i--,n--;
      else D[i].first=abs(CrossPoint(S,G,S2,G2)-S),D[i].second=i;
    }
    

    sort(D,D+n);
    int ans=0,pos=l[D[0].second];
    if(!o[D[0].second]) pos =!pos;
    for(int i=1;i<n;i++) {
      int I=D[i].second;
      if(o[I]&&pos!=l[I])pos=!pos,ans++;
      if(!o[I]&&pos==l[I])pos=!pos,ans++;
    }
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1180
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
#define trav(a, x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9 + 7; // 998244353; // = (119<<23)+1
const int MX = 2e5 + 5;

template<class T>
bool ckmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}

template<class T>
bool ckmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template<typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template<typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template<class X, class Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> const &p) {
    return os << p.first << " " << p.second;
}

template<class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, Container const &x) {
    bool first = true;
    for (auto &y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}

using namespace std;

class BIronBarCutting {
public:
    void solve(std::istream &in, std::ostream &out) {
        int n;
        in >> n;
        vl A(n);
        in >> A;
        ll res = LONG_LONG_MAX;
        ll left = 0, right = accumulate(all(A), 0ll);
        FOR(i, 0, n - 1) {
            left += A[i];
            right -= A[i];
            ckmin(res, abs(right - left));
        }
        out << res << '\n';
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    BIronBarCutting solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 1792
/*I wanna be the very best, like no one ever was...*/

#include<bits/stdc++.h>
using namespace std;
/*******  All Required define Pre-Processors and Constants    *******/

#define ll long long
#define ull unsigned long long 
#define ld long double
#define mem(a, b) memset(a, (b), sizeof(a))
#define rep(i, j, k) for (int i = j ; i < k ; ++i)
#define rrep(i, j, k) for (int i = j; i > k; --i)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(i, a) for(auto i: a)
#define forEach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define in(A, B, C) assert( B <= A && A <= C)
#define debug(a) cout << #a << ": " << a << endl
#define Flag(n) cout << "here " << n << endl
#define mp make_pair
#define pb push_back

#define endl '\n';
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll POSITIVE_INFINITY = 9223372036854775807;
const ll NEGATIVE_INFINITY = -9223372036854775807;
const ll MOD = 1000000007;
const ld PI = acos(-1.0);
 

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr<<name<<" : "<<arg1<<endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif


int pow(int a , int n ){
    long result=1;
            for(long i=0; i<n/2; i++){
                result=result*2;
                result=result%(1000000000+7);
            }
            
            // cout << result << endl;
    return result;
}

int pow2(int a , int n ){
    ll res =1;
    n = n/2;
    while(n){
        if(n%2==1){
            res= (res*a)%MOD;
        }
        a=((a%MOD)*(a%MOD))%MOD;
        n/=2;
    }
    return res;
}


int main() {
    io;
    // freopen("in","r",stdin); 
    // freopen("out","w",stdout);
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    int flag = 1;
    sort(all(v));
    if(n%2==0){
        int start = 1;
        for(int i =0;i<n;i+=2){
            if(v[i]==start && v[i+1]==start){
                start+=2;

            }
            else {
                flag = 0;
                break;
            }

        }
        if(flag){
            // see(n/2);
            // cout<<pow(3,9);
            cout<<pow2(2,n)<<endl;
            return 0;
        }
        else {
            cout<<0<<endl;
            return 0;
        }
    }
    else {
        // see("fasdfa");
        int start = 0;
        if(v[0]!=start){
            flag = 0;
        }
        start+=2; 

       for(int i =1;i<n;i+=2){
        

            if(v[i]==start && v[i+1]==start){
                start+=2;
            }
            else{
                // see(v[i]);
                flag = 0;
                break;
            }
        }

        if(flag){
            
            cout<<pow2(2,n)<<endl;
            return 0;
        }
        else {
            cout<<0<<endl;
            return 0;
        }



    }

 
 
 
    
 
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
vector<int>primes;
void set_prime(int i) {
	for (int j = 2; j * j <= i; j++){
		if (i % j == 0)return;
	}
	primes.push_back(i);
}
bool prime(int a) {
	if (a == 1)return false;
	for (auto i : primes) {
		if (a % i == 0 && i != a)return false;
	}
	return true;
}
int main(){
	for (int i = 2; i <= 9973; i++)set_prime(i);
	int n, ans = 0;
	cin >> n;
	while (n--) {
		int a;
		cin >> a;
		ans += prime(a);
	}
	cout << ans << endl;
}


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

int n, x, y;

int main() {
  cin >> n >> x >> y;
  vector<int> dist_vec(n, 0);
  for (int ps = 1; ps < n + 1; ps++) {
    for (int pe = ps + 1; pe < n + 1; pe++) {
      dist_vec.at(min(abs(ps - x) + abs(y - pe) + 1, abs(ps - pe)))++;
    }
  }
  for (size_t i = 1; i < n; i++) {
    cout << dist_vec.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<queue>
#include<string>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<vector>
#include<functional>

using namespace std;

#ifdef DEBUG
#define dprintf      printf
#define dout(x)      cout<<#x" = "<<(x)<<endl
#define darray(x,n)  {int i;rep(i,n)cout<<#x"["<<i<<"] = "<<*((x)+i)<<endl;}
#define dloop(i,s,g) for(int (i)=(s);(i)<(g);(i)++)
#define drep(i,n)    for(int (i)=0;(i)<(n);(i)++)
#define dstop()      scanf("%*c")
#else
#define dprintf      (1)?0:printf
#define dout(x)
#define darray(x,n)
#define dloop(i,s,g) if(1){}else
#define drep(i,n)    if(1){}else
#define dstop()      if(1){}else
#endif

#define F    first
#define S    second
#define pb   push_back
#define mp   make_pair

#define loop(i,s,g) for(int (i)=(s);(i)<(g);(i)++)
#define rep(i,n)    for(int (i)=0;(i)<(n);(i)++)
#define all(x)      (x.begin(),x.end())
#define in(T,...) T __VA_ARGS__; impl(__VA_ARGS__);
#define array(T,id,n) T id[n]; rep(i,n)cin>>id[i];

//#define int long long;
#ifndef int
#define INF (0x7fffffff)
#else
#define INF (0x7fffffffffffffff)
#endif

typedef  long long           ll;
typedef  unsigned            ui;
typedef  unsigned long long  ull;
typedef  pair<int,int>       i_i;
typedef  pair<ll,int>        ll_i;
typedef  pair<ll,ll>         ll_ll;
typedef  pair<double,int>    d_i;
typedef  pair<double,double> d_d;

void impl(){};
template <typename T,typename... TS >
void impl(T &head,TS &... tail)
{
  cin>>head;
  impl(tail ...);
}

signed main(void)
{
  int ans;
  in(int,a,b,c,d);
  if(a>c)
    {
      ans=d-a;
      if(d>b)
	ans=b-a;
    }
  else
    {
      ans=b-c;
      if(b>d)
	ans=d-c;
    }
  
  if(ans<0)
    puts("0");
    else
    cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
n,t=[int(i) for i in input().split()]
l=[]
def f(l,L,t):
  if L[1] <= t:
    l.append(L[0])
  return l
for i in range(n):
  L=[int(i) for i in input().split()]
  f(l,L,t)
if l==[]:
  print("TLE")
else:
  print(min(l))

Measured memory_bytes: 3316
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  int N; cin >> N;
  vector<ll> A(N+1), B(N);
  for(int i = 0; i < N+1; ++i) {
    cin >> A[i];
  }
  for(int i = 0; i < N; ++i) {
    cin >> B[i];
  }

  ll ans = 0;

  for(int i = 0; i < N; ++i) {
    ll diff = min(A[i], B[i]);
    A[i] -= diff;
    B[i] -= diff;
    ans += diff;
    diff = min(A[i+1], B[i]);
    A[i+1] -= diff;
    B[i] -= diff;
    ans += diff;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792
def solve():
    x, n = map(int, input().split())

    if not n:
        print(x)
        return

    ps = list(map(int, input().split()))
    flgs = [1] * 102

    for p in ps:
        flgs[p] = 0

    ansr = 101
    ansl = 101
    index = x
    while 1:
        if flgs[index] == 1:
            ansr = index
            break
        else:
            index += 1

    index = x
    while 1:
        if flgs[index] == 1:
            ansl = index
            break
        else:
            index -= 1

    if abs(ansr - x) >= abs(ansl - x):
        print(ansl)
    else:
        print(ansr)


solve()


Measured memory_bytes: 9220
#include <stdio.h>

int main() {
    
    long long int TC, n, m, ans;

    scanf("%lld %lld", &m , &n);
    m = m - 1;
    m = (m >> 1) & 1 ^ (m & 1? 1 : m);
    n = (n >> 1) & 1 ^ (n & 1 ? 1 : n);
    ans = m ^ n;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 128
X,Y=map(int,input().split())

ans=0

if X==1:
    ans+=300000
if X==2:
    ans+=200000
if X==3:
    ans+=100000
if Y==1:
    ans+=300000
if Y==2:
    ans+=200000
if Y==3:
    ans+=100000
if X==1 and Y==1:
    ans+=400000

print(ans)

Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val (R, S, P) = readLine()!!.split(" ").map { it.toLong() }
    val t = StringBuilder(readLine()!!)
    val m = mapOf('r' to P, 's' to R, 'p' to S, 'x' to 0L)

    (k until t.length).forEach {
        if (it < k) return@forEach
        if (t[it] == t[it - k]) t[it] = 'x'
    }

    println(t.map { m[it] ?: 0L }.sum())
}


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

using namespace std;

int main(void){
    int n, m;
    cin >> n >> m;
    vector<string> a(n+1, "no");
    vector<int> waNum(n+1, 0);
    int ac = 0, wa = 0;
    for(int i = 0; i < m; i++){
        int num;
        string result;
        cin >> num >> result;
        if(a[num] == "AC") continue;
        if(result == "AC"){
            ac++;
            wa += waNum[num];
        }else{
            waNum[num]++;
        }
        a[num] = result;
    }
    cout << ac << " " << wa << endl;
    return 0;
}

Measured memory_bytes: 6144
using System;

namespace _0511
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] student = new int[31];
            for (int i = 0; i < 28; i++)
            {
                student[int.Parse(Console.ReadLine())] = 999;
            }
            for (int i = 1; i < 31; i++)
            {
                if(!(student[i]==999))
                {
                    Console.WriteLine(i);
                }
            }
        }
    }
}

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

int n, k;
int memo[100010][2];
int a[110];

int dp(int i, int t){
  if(memo[i][t] != -1) return memo[i][t];

  if(t == 0){
    int fin = 0;
    for(int j = 0;j < n;j++){
      if(i-a[j] >= 0 && dp(i-a[j], 1) == 1){
        fin = 1;
        break;
      }
    }
    return memo[i][t] = fin;
  }else{
    int fin = 1;
      for(int j = 0;j < n;j++){
        if(i-a[j] >= 0 && dp(i-a[j], 0) == 0){
          fin = 0;
          break;
        }
      }
      return memo[i][t] = fin;
  }
}

int main(){
  cin >> n >> k;

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

  memset(memo, -1, sizeof(memo));

  if(dp(k, 0) == 1){
    cout << "First" << endl;
  }else{
    cout << "Second" << endl;
  }

  return 0;
}

Measured memory_bytes: 5760
using System;

namespace Test
{
	class Program
	{
		static void Main(string[] args)
		{
			int top1 = 0;
			int top2 = 0;
			int top3 = 0;
			for (int i = 0; i < 10; i++)
			{
				int n = int.Parse(Console.ReadLine());


				if (n > top1)
				{
					top3 = top2;
					top2 = top1;
					top1 = n;
				}
				else if (n > top2)
				{
					top3 = top2;
					top2 = n;
				}
				else if (n > top3)
				{
					top3 = n;
				}
			}
			Console.WriteLine(top1);
			Console.WriteLine(top2);
			Console.WriteLine(top3);
		}
	}
}

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

int main(void){
    int n, m;
    cin >> n >> m;
    
    bool g[51][51] = {{false}};
    int a, b;
    int i;
    for(i = 1; i <= m; i++){
        cin >> a >> b;
        g[a][b] = true;
        g[b][a] = true;
    }
    
    int ans = 0, cnt;
    int node;
    int j;
    for(i = 1; i <= n; i++){
        cnt = 0;
        for(j = 1; j <= n; j++){
            if(g[i][j]){
                cnt++;
                node = j;
            }
            if(cnt >= 2){
                break;
            }
        }
        if(cnt == 1){
            ans++;
            g[i][node] = false;
            g[node][i] = false;
            i = 0;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(){
    int T,n,c,t,i,temp=9999;
    scanf("%d %d",&n,&T);
    for(i=0;i<n;i++){
        scanf("%d %d",&c,&t);
        if(t<=T){
            if(c<temp){
                temp=c;
            }
        }
    }
    if(temp==9999){
        printf("TLE\n");
    }
    else{
        printf("%d\n",temp);
    }
    return 0;
}


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

int main()
{
    long long n, sum = 0;
    scanf("%lld", &n);
    for(long long i = 1; i <= n; i++)
    {
        if(i % 3 == 0 || i % 5 == 0)
            continue;
        else
            sum += i;
    }
    printf("%lld", sum);
    return 0;
}


Measured memory_bytes: 3828
def is_pa(s):
    s = s.casefold()
    rev = reversed(s)
    return list(s)==list(rev)
S = input()
N = len(S)
if is_pa(S) and is_pa(S[0:int((N-1)/2)]) and is_pa(S[int((N+3)/2)-1:]):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
n = gets.chomp.to_i

i = 0
while (i+=1) <= n
	x = i
	if x % 3 == 0 then
		print " #{i}"
		next
	end
	
	while x != 0 do
		if x % 10 == 3 then
			print " #{i}"
			break
		end
		x /= 10
	end
end

puts

Measured memory_bytes: 6092
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;


typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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



    int N, W;
    cin >> N >> W;

    int a[N][2];
    REP(i,N) cin >> a[i][0] >> a[i][1];

    const long long INF = 1LL << 30;
    long long dp[N+1][100000];
    REP(i,N+1)REP(j,W+1)  dp[i][j] = -INF;
    REP(i,W+1) dp[0][i] = 0;

    REP(i,N)REP(w,W+1){
        chmax(dp[i+1][w],dp[i][w]);
        if (w>=a[i][0]) chmax(dp[i+1][w],dp[i][w-a[i][0]]+a[i][1]);
    }

//    REP(i,N+1){
//        REP(j,W+1){
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }

    cout << dp[N][W] << endl;

    return 0;
}

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

int a[100040];

int main()
{

    int n,t2=0,f4=0,ot=0,i,ans;
    scanf("%d",&n);

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

        if(a[i]%4==0) f4++;
        else if(a[i]%2==0) t2++;
        else ot++;
    }

    //printf("%d %d %d\n",f4,t2,ot);

    if(t2==0)
    {
        if(f4>=ot-1) ans=1;
        else ans=0;
    }

    else{
        if(f4>=ot) ans=1;
        else ans=0;
    }

    if(ans==0) printf("No");
    else printf("Yes");

    return 0;
}






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

int main() {
  int A , B , C , D ;
  cin >> A >> B >> C >> D ;
  if ((A + B) == (C + D)){
    cout << "Balanced" << endl;
  }else if((A + B) < (C + D)){
    cout << "Right" << endl;
  }else{
    cout << "Left" << endl;
  }
}

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

int main(){
  int numOfInput, waste = 0;
  cin >> numOfInput;
  vector<int> mochis(numOfInput);
  for(int i = 0; i < numOfInput; i++) cin >> mochis.at(i);
  for(int i = 0; i < numOfInput; i++){
    if(mochis.at(i) == -1) continue;
    for(int j = 0; j < numOfInput; j++){
      if(i == j) continue;
      if(mochis.at(i) == mochis.at(j)){
        mochis.at(j) = -1;
        waste++;
      }
    }
  }
  cout << numOfInput - waste << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int h,w,i,k,j;
    for(k=0;;k++)
    {
    scanf("%d%d",&h,&w);
    if(h==0&&w==0)
    {
        break;
    }
    for(i=0;i<h;i++)
    {
        for(j=0;j<w;j++)
        {
            printf("#");
        }
        printf("\n");
    }
    printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2036
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_A = 2e5 + 24;
const int INF = 1e9 + 7;
int last[MAX_A];
pair <int, pair <int, int> > dp[MAX_A];
string s;
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    int sz = s.size();
    for(int i = 0; i < sz; ++ i)   dp[i].first = INF;
    for(int i = 0; i < 26; ++ i)   last[i] = sz + 2;
    for(int i = sz; i >= 0; -- i)
    {
        for(int j = 0; j < 26; ++ j)
        {
            if(last[j] == sz + 2)
            {
                dp[i].first = 0;
                dp[i].second.first = sz + 2;
                dp[i].second.second = j;
                break;
            }
            if(dp[i].first > dp[last[j] + 1].first)
            {
                dp[i].first = dp[last[j] + 1].first;
                dp[i].second.first = last[j] + 1;
                dp[i].second.second = j;
            }
        }
        ++ dp[i].first;
        if(i - 1 >= 0)   last[s[i - 1] - 'a'] = i - 1;
    }
    for(int i = 0; i <= sz; i = dp[i].second.first)
    {
        char c = dp[i].second.second + 'a';
        cout << c;
    }
    cout << "\n";
	return 0;
}


Measured memory_bytes: 3092
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <functional>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 100000000
template<class T, class C> void chmax(T& a, C b) { a>b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a<b ? : a = b; }

int h, w, n;
char c[1005][1005];
int chx[15] = { 0 }, chy[15] = { 0 }, dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 }, d[1005][1005] = { 0 };
typedef pair<int, int>P;

int bfs(int sx,int sy,int gx,int gy) {
	for (int i = 0; i < 1005; i++) {
		for (int j = 0; j < 1005; j++) {
			d[i][j] = -1;
		}
	}
	queue<P>que;
	que.push(P(sx, sy));
	d[sx][sy] = 0;
	while (que.size()) {
		P p = que.front();
		que.pop();
		int nowx = p.first;
		int nowy = p.second;
		//cout << nowx << " " << nowy << endl;
		if (nowx == gx&&nowy == gy) break;
		for (int i = 0; i < 4; i++) {
			int nx = nowx + dx[i];
			int ny = nowy + dy[i];
			if (d[nx][ny]==-1&&0 <= nx&&nx < h && 0 <= ny&&ny < w&&c[nx][ny]!='X') {
				d[nx][ny] = d[nowx][nowy] + 1;
				que.push(P(nx, ny));
			}
		}
	}
	return d[gx][gy];
}

int main() {
	cin >> h >> w >> n;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> c[i][j];
			if (c[i][j] == 'S') {
				chx[0] = i;
				chy[0] = j;
			}
			else if ('1' <= c[i][j] && c[i][j] <= '9') {
				int number = c[i][j] - '0';
				chx[number] = i;
				chy[number] = j;
			}
		}
	}
	int cnt = 0;
	for (int i = 0; i <= n - 1; i++) {
		cnt += bfs(chx[i], chy[i], chx[i + 1], chy[i + 1]);
	}
	cout << cnt << endl;
	return 0;
}

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

int main(){
	int N, M, C;
	int sum;
	int num = 0;
	int A[25], B[25];
	cin >> N >> M >> C;
	for(int i = 1; i <= M; i++)
	cin >> B[i];
	while(N--){
		sum = 0;
		for(int i = 1; i <= M; i++){
			cin >> A[i];
			sum += A[i]*B[i];
		}
		sum += C;
		if(sum > 0)
		num++;
	}
	cout << num;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MODNum 1000000007
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    string S, T;
    cin >> S;
    cin >> T;
    REP(int,i,0,S.size()){
        if ( S.at(i) != T.at(i) ){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3632
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String str;
		int num[]=new int[51];
		for (int i = 0; i <= 9; i++) {
			for (int j = 0; j <= 9; j++) {
				for (int k = 0; k <= 9; k++) {
					for (int l = 0; l <= 9; l++)
						num[i+j+k+l]++;
				}
			}
		}
		while (null != (str = in.readLine())) {
			System.out.println(num[Integer.parseInt(str)]);
		}
	}
}

Measured memory_bytes: 16864
import java.util.*;

public class Main{
	public static void main(String[] args){

		Scanner scan = new Scanner(System.in);
		String str = scan.next();
		String s1, s2;
		int q = scan.nextInt();
		int len = str.length();
		for(int i = 0; i < q; i++){
			String com = scan.next();
			if(com.equals("print")){
				int a = scan.nextInt();
				int b = scan.nextInt();
				s1 = str.substring(a, b + 1);
				System.out.println(s1);
			}
			if(com.equals("reverse")){
				int a = scan.nextInt();
				int b = scan.nextInt();
				s1 = str.substring(0, a);
				s2 = str.substring(b + 1, len);
				StringBuffer sb = new StringBuffer();
				for(int j = b; j >= a; j--){
					sb.append(str.charAt(j));
				}
				str = s1 + sb + s2;
			}
			if(com.equals("replace")){
				int a = scan.nextInt();
				int b = scan.nextInt();
				String p = scan.next();
				s1 = str.substring(0, a);
				s2 = str.substring(b + 1);
				str = s1 + p + s2;
			}
		}
	}
}

Measured memory_bytes: 29704
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    sort( s.begin(), s.end() );
    if (s[1] == s[2] == s[3] == '0') cout << "Yes";
    else if (s[0] == s[1] && s[0] == s[2]) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 3584
#include<algorithm>
#include<cstdio>
#include<iostream>
const int N=55;
int a[N];
int main() {
    int n;
    std::cin>>n;
    for(int i=1;i<=n;i++) std::cin>>a[i];
    std::sort(a+1,a+1+n);
    double now=a[1];
    for(int i=2;i<=n;i++) now=(now+a[i])/2;
    std::cout<<now;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 123;
int n, t[2][N], h[N], sz;
ll l;

ll g(ll x) {
	if (x == 0) return 0;
	ll res = 1;
	while (x % 2 == 0)
		x /= 2, res *= 2;
	return res;
}

void add(string s) {
	int v = 0;
	for (int i = 0; i < (int)s.size(); i++) {
		if (!t[s[i] - '0'][v])
			t[s[i] - '0'][v] = ++sz;
		v = t[s[i] - '0'][v];
	}
}

ll res;

void dfs(int v) {
	int child = 0;
	for (int i = 0; i < 2; i++) {
		int to = t[i][v];
		if (to) {
			h[to] = h[v] + 1;
			dfs(to);
			child++;
		}
	}
	if (child == 1)
		res ^= g(l - h[v]);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> l;
	string s;
	for (int i = 0; i < n; i++) cin >> s, add(s);
	dfs(0);
	if (res == 0) cout << "Bob";
	else cout << "Alice";
}


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

int main(void) {
  int n,i, count=0;
  scanf("%d",&n);
  int a;
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    if (i % 2 == 0 && a % 2 == 1) count++;
  }
  printf("%d", count);
  return 0;
}

Measured memory_bytes: 1736
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it;}cout<<endl;}

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

int main() {
    ll n,m;
    cin>>n>>m;
    vector<ll> p(n);
    rep(i, n) cin>>p[i];
    vector<unordered_set<ll>> v(n);
    
    auto u = UnionFind(1000000);
    rep(i, n) v[i].insert(p[i]);
    rep(i, m){
        ll x,y;
        cin>>x>>y;
        u.unionSet(x, y);
//        v[x-1].insert(p[y-1]);
//        v[y-1].insert(p[x-1]);
    }
    ll sum=0;
    rep(i, n) if(u.findSet(i+1, p[i])) sum++;
    pr(sum);
//    pr(u.findSet(1, 2));
//    pr(u.findSet(3, 1));
}



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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

typedef long long int ll;

int main() {
    int n = 3;
    vector<int> v(n);
    rep(i, n) { cin >> v[i]; }
    sort(all(v));

    if (v[0] == v[1] && v[1] != v[2])
    {
        cout << "Yes" << endl;
  } else if (v[1] == v[2] && v[0] != v[1]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

using namespace std;
typedef long long ll;
struct xl
{
    ll x,l,r,d;
} xl[100005];
int vis[100050];
bool cmp(struct xl a,struct xl b)
{
    return a.x<b.x;
}
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        scanf("%lld%lld",&xl[i].x,&xl[i].d);
        xl[i].l=xl[i].x-xl[i].d;
        xl[i].r=xl[i].x+xl[i].d;
    }
    sort(xl,xl+n,cmp);
    stack<ll> st;
    ll wz=-1e9+7;
    st.push(0);
    wz=xl[0].l;
    for(int i=1; i<n; i++)
    {
        int t=st.top();
        if(wz<=xl[i].l&&xl[i].r<=xl[t].r)
        {
            st.pop();
            if(!st.empty())
                wz=xl[st.top()].r;
            else
                wz=-1e9+7;
            st.push(i);
        }
        else if(xl[i].l>=xl[t].r)
        {
            wz=xl[st.top()].r;
            st.push(i);
        }
        else
        {
            continue;
        }
    }
    printf("%d\n",st.size());

    return 0;
}

Measured memory_bytes: 4224
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 X = sc.nextInt();
		int Y = sc.nextInt();
		int count = 0;
		
		int xnMax = -99999999, ymMin = 99999999;

		for (int i = 0; i < N; i++) {

			int xn = sc.nextInt();
			xnMax = Math.max(xnMax, xn);
		}
		for (int i = 0; i < M; i++) {
			int ym = sc.nextInt();
			ymMin = Math.min(ymMin, ym);
		}

		for (int i = X+1; i <= Y; i++) {
			if(xnMax < i && ymMin >= i) {
			++count;
			}
		}
		if(count == 0) {
			System.out.println("War");
		}else {
			System.out.println("No War");
		}

	}

}



Measured memory_bytes: 23764
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
using ll = long long;

ll X,K,D;

int main(void){

    ll ans;
    cin >> X >> K >> D;
    if (X < 0) X = X * (-1);

    ll ap = X / D;
    if (ap >= K) {
        ans = X - K * D;
    } else{
        ll rest = K - ap;
        ll st = X - ap * D;
        if (rest % 2 == 0){
            ans = st;
        } else {
            ans = D - st;
        }
    }


    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
   int n; cin >> n;
   map<string, int> mp;
   rep(i,n){
      string t; cin >> t;
      mp[t]++;
   }

   for(auto x:mp){
      if(mp["AC"]==0){
         cout << "AC x " << 0 << endl;
         break;
      }
      if(x.first == "AC"){
         cout << "AC x " << x.second << endl;
      }
   }

   for(auto x:mp){
      if(mp["WA"]==0){
         cout << "WA x " << 0 << endl;
         break;
      }
      if(x.first == "WA"){
         cout << "WA x " << x.second << endl;
      }
   }

   for(auto x:mp){
      if(mp["TLE"]==0){
         cout << "TLE x " << 0 << endl;
         break;
      }
      if(x.first == "TLE"){
         cout << "TLE x " << x.second << endl;
      }
   }

   for(auto x:mp){
      if(mp["RE"]==0){
         cout << "RE x " << 0 << endl;
         break;
      }
      if(x.first == "RE"){
         cout << "RE x " << x.second << endl;
      }
   }

   return 0;
}


Measured memory_bytes: 3636
function Main(input) {
  input = input.split("\n");
  var s = input[0];
  a = new Array(4).fill(0);
  for(i=0;i<4;i++){
    a[i]=parseInt(s.substr(i,1));
  }
  var ans = "";
  var b = 7-a[0];
  if(a[1]+a[2]+a[3]==b){
    ans=a[0] + "+" + a[1] + "+" + a[2] + "+" + a[3] + "=7";
  }else if(-a[1]+a[2]+a[3]==b){
    ans=a[0] + "-" + a[1] + "+" + a[2] + "+" + a[3] + "=7";
  }else if(a[1]-a[2]+a[3]==b){
    ans=a[0] + "+" + a[1] + "-" + a[2] + "+" + a[3] + "=7";
  }else if(a[1]+a[2]-a[3]==b){
    ans=a[0] + "+" + a[1] + "+" + a[2] + "-" + a[3] + "=7";
  }else if(-a[1]-a[2]+a[3]==b){
    ans=a[0] + "-" + a[1] + "-" + a[2] + "+" + a[3] + "=7";
  }else if(-a[1]+a[2]-a[3]==b){
    ans=a[0] + "-" + a[1] + "+" + a[2] + "-" + a[3] + "=7";
  }else if(a[1]-a[2]-a[3]==b){
    ans=a[0] + "+" + a[1] + "-" + a[2] + "-" + a[3] + "=7";
  }else if(-a[1]-a[2]-a[3]==b){
    ans=a[0] + "-" + a[1] + "-" + a[2] + "-" + a[3] + "=7";
  }
  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
//
//  second.cpp
//  CoderTest
//
//  Created by yuya on 2019/07/25.
//  Copyright Â© 2019 yuya. All rights reserved.
//

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

int main()
{
    int X, Y;
    int prize = 0;
    cin >> X >> Y;
    X = 4 - X;
    Y = 4 - Y;
    if (X > 0)
        prize += X * 100000;
    if (Y > 0)
        prize += Y * 100000;

    if (X == 3 && Y == 3)
        prize += 400000;

    cout << prize << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

// namespace
using namespace std;

const int N = 8;
int dx[8] = {0, 1, 1,  1, -1, -1,  0, -1};
int dy[8] = {1, 1, 0, -1,  0, -1, -1,  1};

void set_val(int x, int y, int a[8][8], int pos[8], int val) {
    if (val > 0) pos[x] = y;
    else pos[x] = -1;
    a[x][y] += val;
    for (int k = 0; k < 8; ++k) {
        for (int l = 1; l < 8; ++l) {
            int next_x = x + l * dx[k];
            int next_y = y + l * dy[k];
            if (0 <= next_x && next_x < 8 && 0 <= next_y && next_y < 8)
                a[next_x][next_y] += val;
        }
    }
}

void show_board(const int pos[8]) {
    for (int i = 0; i < 8; ++i) {
        for (int j = 0; j < 8; ++j) {
            cout << (pos[i] == j ? 'Q' : '.');
        }
        cout << endl;
    }
}

bool solve_queen(int col, int a[8][8], int pos[8]) {
    if (col == 8) return true;
    if (pos[col] != -1) return solve_queen(col + 1, a, pos);
    for (int row = 0; row < 8; ++row) {
        if (a[col][row] == 0) {
            set_val(col, row, a, pos, +1);
            bool success = solve_queen(col + 1, a, pos);
            if (success) return true;
            set_val(col, row, a, pos, -1);
        }
    }
    return false;
}

int main() {
    int a[N][N];
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
            a[i][j] = 0;
    int pos[8];
    for (int i = 0; i < 8; ++i) pos[i] = -1;

    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        set_val(x, y, a, pos, true);
    }

    solve_queen(0, a, pos);
    show_board(pos);

   return 0;
}



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

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

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

int main(void) {
	int n;
	int y[101];
	int m[101];
	int d[101];
	int res[101] = {};

	cin >> n;
	FOR(i, 1, n) {
		cin >> y[i] >> m[i] >> d[i];
	}
	FOR(i, 1, n) {
		FOR(t, y[i] + 1, 999) {
			if (t % 3 == 0) {
				res[i] += 200;
			}
			else {
				res[i] += 195;
			}
		}
		if (y[i] % 3 == 0) {
			res[i] += (10 - m[i]) * 20;
			res[i] += (20 - d[i]);
		}
		else {
			if (m[i] % 2==0) {
				res[i] += (19 - d[i]);
			}
			else {
				res[i] += (20 - d[i]);
			}
			FOR(u, m[i] + 1, 10) {
				if (u % 2 == 0) {
					res[i] += 19;
				}
				else {
					res[i] += 20;
				}
			}
		}
		res[i]++;
	}
	FOR(i, 1, n) {
		cout << res[i] << endl;
	}
}


Measured memory_bytes: 3008
//Link : https://atcoder.jp/contests/abc155/tasks/abc155_f

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

pair<int,int> in[N];
int bit[N];
vector<pair<int,int> >adj[N];
vector<int> out;
bool vis[N];
int parity[N];
int dfs(int node) {
  parity[node] = bit[node];
  vis[node] = true;
  for(pair<int,int> ch : adj[node]) {
    if(!vis[ch.first]) {
      dfs(ch.first);
      parity[node] ^= parity[ch.first];

      if(parity[ch.first]==1) {
        out.push_back(ch.second);
      }
    }
  }
  return parity[node];
}

int ar[N];
void solve() {
  int n,m;scanf("%d %d ", &n,&m);

  vector<int> xs;
  for(int i=0;i<n;++i) {
    scanf("%d %d ", &in[i].first,&in[i].second);
    ar[i] = in[i].first;
  }
  in[n].first = 2e9;
  sort(in,in+n);
  bit[0] = in[0].second;
  for(int i=n;i;--i) {
    in[i].second^= in[i-1].second;
    bit[i] = in[i].second;
  }
  for(int i=0;i<m;++i) {
    int x,y;
    scanf("%d %d ", &x,&y);
    int l = lower_bound(in,in+n+1,make_pair(x,-15)) - in;
    int r = lower_bound(in,in+n+1,make_pair(y+1,-15))-in;
    if(l!=r) {
      adj[r].push_back(make_pair(l,i+1));
      adj[l].push_back(make_pair(r,i+1));
    }
  }

  for(int i=0;i<=n;++i) {
    if(!vis[i]) {
      if(dfs(i)) {
        printf("-1\n");
        return;
      }
    }
  }
  printf("%d\n", out.size());
  sort(out.begin(),out.end());
  for(int edge : out) {
    printf("%d ", edge);
  }
  putchar('\n');
}

int main() {
    //freopen("input.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 17788
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	string s, ans;
	cin >> s;
	ans = s[0] + to_string(s.size() - 2) + s[s.length() - 1];
	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) ll((a).size())
#define out(a) cout<<(a)<<endl;
const int inf=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;


vll par(MAX),siz(MAX);

//par[i]=iならiは根（はじめは全て根）
void init(ll n){
  rep(i,0,n){
    par[i]=i;siz[i]=1LL;
  }
  return;
}
//xの根
ll root(ll x){
  return (par[x]==x)?x:par[x]=root(par[x]);
}
//xが根の木とyが根の木を繋げる
void unite(ll x,ll y){
  x=root(x);y=root(y);
  if(x==y){return;}
  if(siz[x]<siz[y]){swap(x,y);}
  siz[x]+=siz[y];
  par[y]=x;
}
//根が同じかどうか
bool same(ll x,ll y){
  return root(x)==root(y);
}
int main(){
  ll n,m;cin>>n>>m;
  init(n);
  rep(i,0,m){
    ll x,y,z;cin>>x>>y>>z;
    unite(x-1,y-1);
  }
  set<ll>s;
  rep(i,0,n){
    
    s.insert(root(i));
  }
  cout<<s.size()<<endl;
}



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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    int H, W;
    cin >> H >> W;
    int h, w;
    cin >> h >> w;
    int ans = 0;

    // 処理
    // ans = W * H - (H * w + W * h - w * h);
    ans = (W - w) * (H - h);
    cout << ans << endl;

    // 出力

    return 0;
}


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

#define TEXT_SIZE 1000001
#define PAT_SIZE 10001
#define ASCII 123

void countup(int *accumulate, int pCmp, int value) { accumulate[pCmp] = value; }

void undefined(int *, int, int) {}

int setCompress(char *text, int **compress, int *accumulate, int len, void(*func)(int*, int, int)) {
	int result = 0;
	int pCmp = -1;
	char ch = '*';
	for (int i = 0; i < len; i++) {
		if (text[i] != ch) {
			compress[0][++pCmp] = int(text[i]);
			ch = text[i];
			result++;
		}
		compress[1][pCmp]++;
		func(accumulate, pCmp, i + 1);
	}
	return result;
}

int main() {
	char text[TEXT_SIZE];
	char pat[PAT_SIZE];
	int *compressT[2];
	int *compressP[2];
	int *accumulate;
	int skip[ASCII];
	int i,j, orgTextLen, orgPatLen, pLast, pText, pPat, textLen, patLen;
	cin >> text;
	cin >> pat;

	orgTextLen = strlen(text);
	orgPatLen = strlen(pat);
	
	for (i = 0; i < 2; i++) {
		compressT[i] = (int *)calloc(orgTextLen, sizeof(int));
		compressP[i] = (int *)calloc(orgPatLen, sizeof(int));
	}
	accumulate = (int *)calloc(orgTextLen, sizeof(int));

	textLen = setCompress(text, compressT, accumulate, orgTextLen, countup);
	patLen = setCompress(pat, compressP, NULL, orgPatLen, undefined);

	for (i = 0; i < ASCII; i++) skip[i] = patLen;
	for (i = 0; i < patLen - 1; i++) skip[int(compressP[0][i])] = patLen - i - 1;

	pLast = patLen - 1;
	while (pLast < textLen) {
		pText = pLast;
		pPat = patLen - 1;
		while (compressT[0][pText] == compressP[0][pPat]) {
			if (pPat == 0) {
				for (i = 0; i < patLen; i++) {
					if (i == 0 || i + 1 == patLen) {
						if (compressP[1][i] > compressT[1][pText + i]) break;
					}
					else if (compressP[1][i] != compressT[1][pText + i]) break;
				}
				if (i == patLen) {
					if (patLen == 1) {
						for (j = 0; j <= compressT[1][pText] - compressP[1][0]; j++) {
							cout << accumulate[pText] - compressT[1][pText] + j << endl;
						}
					}
					else {
						cout << accumulate[pText] - compressP[1][0] << endl;
					}
				}
				break;
			}
			pText--;
			pPat--;
		}
		pLast = pLast + skip[int(compressT[0][pLast])];
	}

	for (i = 0; i < 2; i++) {
		free(compressT[i]);
		free(compressP[i]);
	}
	free(accumulate);
	return 0;
}


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

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

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

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

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

using namespace std;

//-------------------------------------------------
//--Z-Algorithm
//-------------------------------------------------
template <class T>
vector<int> z_algo(const T &s){
    int n = s.size();
    vector<int> ret(n); ret[0]=n;
    int i=1,j=0;
    while(i<n){
        while(i+j<n && s[i+j]==s[j]) j++;
        ret[i] = j;
        if (j==0){i++; continue;}
        int k = 1;
        while(i+k<n && k+ret[k]<j) ret[i+k]=ret[k], k++;
        i+=k; j-=k;
    }
    return ret;
}

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vi a(n),b(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    vi T(n);
    rep(i,n) T[i] = b[i]^b[(i+1)%n];
    rep(i,2*n-1) T.pb(a[i%n]^a[(i+1)%n]);
    auto A = z_algo(T);
    int N = A.size();
    FOR(i,n,N-1)if(A[i]>=n){
        int k=i-n;
        cout<<k<<" "<<(b[0]^a[k])<<"\n";
    }
    return 0;
}


Measured memory_bytes: 9684