Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, [dist[v_to], v_to])
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(N):
        br.append(list(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(round(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 12), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        # if v_from == 2:
        #    return dist
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [(xs, ys, 0), (xt, yt, 0)]
    for _ in range(N):
        br.append(tuple(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
# S = input()
# A, B, C, D, E, F = mulinputs()
datas = list(mulinputs())
# datas = lineinputs(input)

M = 1001000
cnt = 0
l = len(datas)
for i in range(0,N):
    is_clear = True
    for j in range(0,(i+1)>>1):
        dp0 = datas[2*j] if 2*j < l else M
        dp1 = datas[2*j+1] if 2*j < l else M
        if dp0 < datas[i]:
            is_clear = False
            break
        if dp1 < datas[i]:
            is_clear = False
            break
    if is_clear:
        cnt += 1

# 出力
print(cnt)




### FIXED CODE ###

# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
# S = input()
# A, B, C, D, E, F = mulinputs()
datas = list(mulinputs())
# datas = lineinputs(input)

M = 1001000
cnt = 0
l = len(datas)
# for i in range(0,N):
#     is_clear = True
#     for j in range(0,(i+1)>>1):
#         dp0 = datas[2*j] if 2*j < l else M
#         dp1 = datas[2*j+1] if 2*j < l else M
#         if dp0 < datas[i]:
#             is_clear = False
#             break
#         if dp1 < datas[i]:
#             is_clear = False
#             break
#     if is_clear:
#         cnt += 1
dmap = dict()
for i in range(1, len(datas)+1):
    dmap[datas[i-1]] = i
counter = N
for i in range(1, len(datas)+1):
    if dmap[i]-1 > counter:
        continue
    counter -= (counter - (dmap[i]-1))
    cnt +=1
    if counter <=0:
        break


# 出力
print(cnt)
### BUGGY CODE ###

from collections import Counter
import math

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n = int(input())
A = list(map(int, input().split()))

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

for i in range(n):
    num = A[i]
    t = counter[num]
    ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
    print(ans)

### FIXED CODE ###

from collections import Counter

mod = (10 ** 9 + 7) ** 5
MAX = 2 * 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

n = int(input())
A = list(map(int, input().split()))

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

memo = {}
for i in range(n):
    num = A[i]
    if num in memo:
        print(memo[num])
    else:
        t = counter[num]
        ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
        print(ans)
        memo[num] = ans
### BUGGY CODE ###

N = int(input().strip())

#n_list = [[] for i in range(N)]
d = [0] * N
connect = [[-1 for i in range(N)] for j in range(N)]
for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    connect[a][b] = i
    connect[b][a] = i
    d[a] += 1
    d[b] += 1

max_index = -1
max_degree = -1
for i in range(N):
    if d[i] > max_degree:
        max_degree = d[i]
        max_index = i

colors = [0] * (N-1)

root = max_index

def paint(node, parent_edge_id):
    tmp_color = 1
    for i in range(N):
        edge_id = connect[node][i]
        if edge_id == -1:
            continue
        if edge_id != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge_id] = tmp_color
            paint(i, edge_id)
            tmp_color += 1

    
try:
    paint(root, -1)
except TypeError:
    print(0)
print(max_degree) # color num    a
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])
### BUGGY CODE ###

N = int(input())
even = True if N % 2 == 0 else False

start = 0
end = N-1

print(0)
s0 = input()
if s0 == 'Vacant':
    exit()

ni = (start+end)//2
print(ni)
s = input()

while s != 'Vacant':
    if not((s == s0) ^ (s % 2 == s0 % 2)):
        start = ni+1
    else:
        end = ni

    s0 = s

    ni = (start+end)//2
    print(ni)
    s = input()

exit()


### FIXED CODE ###

N = int(input())


def ask(i):
    print(i, flush=True)
    resp = input()
    if resp == 'Vacant':
        exit()
    return resp


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp
### BUGGY CODE ###

MOD =  1000000007
res = 0
a = input()
n = len(a)
A = 13
dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    c = 0
    if a[i] == '?': c = -1
    else: c = int(a[i])
    
    for j in range(10):
        if c != -1 and c != j: continue
        for ki in range(13):
            dp[i+1][(ki*10 + j)% 13] += dp[i][ki]
        
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[n][5])


### FIXED CODE ###

MOD =  1000000007
res = 0
a = input()
n = len(a)
A = 13
dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    c = 0
    if a[i] == '?': c = -1
    else: c = int(a[i])
    
    for j in range(10):
        if c != -1 and c != j: continue
        for ki in range(13):
            dp[i+1][(ki*10 + j)% 13] += dp[i][ki]
        
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[n][5])
### BUGGY CODE ###

import collections
N,T=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
for i in range(1,N):
  B[i]=A[i]-min(A[:i])
maxB=max(B)
c=collections.Counter(B)
print(c[maxB])

### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
x=[0]*n
x[0]=a[0]
for i in range(1,n):
    x[i]=min(x[i-1],a[i])
d=dict()
for i in range(1,n):
    y=a[i]-x[i-1]
    if y>0:
        if y in d:
            d[y]+=1
        else:
            d[y]=1
d=list(d.items())
d.sort(reverse=True)
print(d[0][1])
### BUGGY CODE ###

import heapq
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort(reverse=True)
f.sort()
m = []
for i, j in zip(a, f):
    heapq.heappush(m, (-i*j, i, j))
for i in range(k):
    t = heapq.heappop(m)
    heapq.heappush(m, (-(t[1] - 1)*t[2], t[1]-1, t[2]))
    if m[0][0]== 0:
        print(0)
        break
else:
    print(-m[0][0])



### FIXED CODE ###

import math
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort(reverse=True)
    f.sort()
    hi = a[0] * f[-1]
    lo = 0
    def caneat(m):
        t = 0
        for i, j in zip(a, f):
            if i * j > m:
                t += math.ceil((i*j - m)/j)
            if t > k:
                return False
        return True
    while hi != lo:
        m = (hi + lo) // 2
        if caneat(m):
            hi = m
        else:
            lo = m + 1
    return hi
print(main())
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = [0] * (N+1)
ans = [0] * N
for i in range(N):
  cnt[A[i]] +=1
for i in range(N):
  for j in range(N+1):
    if(j == A[i]):
      ans[i] += (cnt[j]-1) * (cnt[j]-2) // 2
    else:
      ans[i] += cnt[j] * (cnt[j]-1) // 2
for i in range(N):
  print(ans[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = [0] * (N+1)
ans = 0
for i in range(N):
  cnt[A[i]] +=1
for i in range(N+1):
  ans += cnt[i] * (cnt[i] - 1) // 2
for i in range(N):
  print(ans - cnt[A[i]] + 1)
### BUGGY CODE ###

n, m = map(int, input().split())
x = [x for x in map(int, input().split())]
y = [y for y in map(int, input().split())]
ans = 0
for i in range(n-1):
    for j in range(m-1):
        v = (i+1)*(n-1-i) * (j+1)*(m-1-j) #面積係数
        x_width = x[i+1] - x[i]
        y_width = y[j+1] - y[j]
        ans += v * x_width * y_width #面積係数*最小長方形面積
print(ans%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
x = [x for x in map(int, input().split())]
y = [y for y in map(int, input().split())]
sum_x = 0
sum_y = 0
ans = 0
for i in range(n):
    sum_x += (2*i - n + 1) * x[i] 
for j in range(m):
    sum_y += (2*j - m + 1) * y[j]
ans = sum_x * sum_y
print(ans%1000000007)
### BUGGY CODE ###

str = raw_input()
K = int(raw_input())

#print str, K,  len(str)

#dic = []
dic = set()

i = 1

while i <= len(str):
    idx = 0
    while True:
        head = idx
        tail = i + idx
        if tail > len(str):
            break
        else:
#            dic.append(str[head:tail])
            dic.add(str[head:tail])
            idx = idx + 1

    i = i + 1


#dic_set = list(set(dic))
#dic_set.sort()
#print dic_set

dic_set = list(dic)
dic_set.sort()


print dic_set[K-1]


### FIXED CODE ###

#import time

str = raw_input()
K = int(raw_input())

#t_start = time.time()

#print str, K,  len(str)

#dic = []
dic = set()

i = 1

#while i <= len(str):
while i <= K:
    idx = 0
    while True:
        head = idx
        tail = i + idx
        if tail > len(str):
            break
        else:
#            dic.append(str[head:tail])
            dic.add(str[head:tail])
            idx = idx + 1

    i = i + 1


#dic_set = list(set(dic))
#dic_set.sort()
#print dic_set

dic_set = list(dic)
dic_set.sort()


print dic_set[K-1]
#print time.time() - t_start
### BUGGY CODE ###

def solve():
    s = input()

    cnt = 0
    for i in range(4, len(s) + 1):
        # print('i',i)
        for j in range(i-4, -1, -1):
            # print(s[j:i])
            n = int(s[j:i])
            if n % 2019 == 0:
                cnt = cnt + 1
    print(cnt)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

R, G, B, N = map(int, input().split())

counter = 0
for r in range(int(N/R) + 1):
    for g in range(int(N/G) + 1):
        if R*r + G*g > N:
            break
        if (N - R*r - G*g) % B == 0:
            counter += 1

print(counter)

### FIXED CODE ###

# -*- coding: utf-8 -*-

R, G, B, N = map(int, input().split())

counter = 0
for r in range(int(N/R) + 1):
    for g in range(int(N/G) + 1):
        t = R*r + G*g
        if t > N:
            break
        if (N - t) % B == 0:
            counter += 1

print(counter)
### BUGGY CODE ###


def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    accum = 0
    for i in range(N+1):
        B[i] = accum
        if i != N:
            accum += A[i]
    
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([i * (i - 1)//2 for i in d.values()]))
        
# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)
if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N, M = [int(n) for n in input().split()]
    A = [int(n) for n in input().split()]
    B = [0]*(N+1)
    B[0] = 0
    d = {}
    accum = 0
    for i in range(N+1):
        B[i] = accum
        if i != N:
            accum += A[i]
    
    for i, b in enumerate(B):
        x = b % M
        if x in d.keys():
            d[x] += 1
        else:
            d[x] = 1
    # print(B)
    print(sum([i * (i - 1)//2 for i in d.values()]))
        
# import os,sys, time

# current = os.path.abspath(__file__ + "/..")+"/"
# fdr = open(current + "d-case1.txt", "r")
# sys.stdin = fdr
# t = time.time()
# main()
# print(time.time() - t)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]
def match(ab):
    a,b=ab
    gpa=friendlist[a]
    gpb=friendlist[b]
    mema=gplist[gpa].copy()
    memb=gplist[gpb].copy()
    if gpa==gpb:
        return
    else:
        gplist[gpa].extend(memb)
        for i in memb:
            friendlist[i]=gpa
        gplist[gpb] = [-1]

# print(gplist)
for i in range(M):
    match(tuple(map(lambda x:int(x)-1,input().split())))
    # print(friendlist)
    # print(gplist)
print(max([len(item) for item in gplist]))

### FIXED CODE ###

N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]

def getgroup(a):
    A = friendlist[a]
    if A == a:
        return a
    else:
        return getgroup(A)

def match(ab):
    A = getgroup(ab[0])
    B = getgroup(ab[1])
    if A==B:
        return
    elif len(gplist[A])<len(gplist[B]):
        gplist[B].extend(gplist[A])
        friendlist[A] = B
    else:
        gplist[A].extend(gplist[B])
        friendlist[B] = A

for i in range(M):
    # print(friendlist)
    # print(gplist)
    match(tuple(map(lambda x:int(x)-1,input().split())))

# print(friendlist)
# print(gplist)

print(max([len(item) for item in gplist]))
### BUGGY CODE ###

k = int(input())
a=7
i=1
while i <= 30000:
  if a%k ==0:
    print(i)
    break
  elif i==30000 and a%k !=0:
    print("-1")
    break
  i+=1
  a = a + 7*10**(i-1)


### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k%5==0:
    print(-1)
    exit()
a = 7
ans = 1
while True:
    if a % k == 0:
        print(ans)
        exit()
    a = (a*10+7) % k
    ans += 1
### BUGGY CODE ###

N, M, K = (int(x) for x in input().split())

def nCm(n,m):
    if m < 0 or m > n:
        return 0
    nf = factorial(n)
    nm = factorial(m)
    nm2 = factorial(n-m)
    return (nf//nm//nm2) % 1000000007

def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i+1)
    return ans

c_sum = (M*(N-1)*N*(N+1)*M+N*(M-1)*M*(M+1)*N)//3
c_sum = c_sum//2
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)


### FIXED CODE ###

import math

N, M, K = (int(x) for x in input().split())

def comb(n,k,p):
    if k < 0 or k > n:
        return 0
    if n == 0 or k == 0:
        return 1
    a=math.factorial(n) % p
    b=math.factorial(k) % p
    c=math.factorial(n-k) % p
    return (a*mypow(b,p-2,p)*mypow(c,p-2,p)) % p

def mypow(a,b,p):
    if b == 0: return 1
    if b % 2 == 0:
        d=mypow(a,b//2,p)
        return d*d % p
    if b % 2 == 1:
        return (a*mypow(a,b-1,p )) % p

c_sum = (M*(N-1)*N*(N+1)*M+N*(M-1)*M*(M+1)*N)//3
c_sum = c_sum//2
c_sum *= comb(N*M-2, K-2, 1000000007)
c_sum = c_sum % 1000000007

print(c_sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

N, M = map(int, input().split())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a*2, b, 0, 0))
for i in range(M):
    l, r = map(int, input().split())
    R.append((l*2-1, 2, -1, i))
    R.append((r*2+1, 3, 2*l-1, i))

R.sort(key=lambda x:x[0])
nodeid = 0
bf = -1
d = dict()
x2id = dict()
id2eid = dict()
G = {0:set()}
for x, f, l, i in R:
    if f <= 1:
        d[nodeid] = int(f != bf and bf != -1)
        bf = f
        nodeid += 1
        G[nodeid] = set()
    else:
        x2id[x] = nodeid
        if f == 3:
#            print(x2id, l)
            G[nodeid].add(x2id[l])
            G[x2id[l]].add(nodeid)
            id2eid[(nodeid, x2id[l])] = i
            id2eid[(x2id[l], nodeid)] = i
d[nodeid] = int(bf == 1)

def iterf(v):
    r = d[v]
    for u in G[v]:
        if u in vs:
            continue
        vs.add(u)
        avs.add(u)
        ff = iterf(u)
        if ff:
            cut_edges.add((v, u))
        r = (r+ff)%2
    return r if v != 0 else 0

xxs = [-1]*nodeid
avs = set()
cut_edges = set()
for i in range(nodeid+1):
    if i in avs:
        continue
    vs = set([i])
    rr = iterf(i)
    if rr:
        print(-1)
        break
else:
#    print(G)
#    print(d)

    print(len(cut_edges))
    print(*sorted(id2eid[(x, y)]+1 for x, y in cut_edges))


### FIXED CODE ###

import sys
input = sys.stdin.readline
LLL = 1<<20

N, M = map(int, input().split())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a*2, b, 0))
for i in range(M):
    l, r = map(int, input().split())
    R.append((l*2-1, 2, i))
    R.append((r*2+1, 3, i))

R.sort(key=lambda x:x[0])
nodeid = 0
bf = -1
d = []
eid2lid = dict()
id2eid = dict()
G = [set()]
for x, f, i in R:
    if f <= 1:
        d.append(int(f != bf and bf != -1))
        bf = f
        nodeid += 1
        G.append(set())
    else:
        if f == 3:
#            print(x2id, l)
            lid = eid2lid[i]
            if nodeid != lid:
                G[nodeid].add((lid, i+1))
                G[lid].add((nodeid, i+1))
#                id2eid[lid*LLL+nodeid] = i
#            id2eid[(n2, n1)] = i
        eid2lid[i] = nodeid
d.append(int(bf==1))

xxs = [-1]*(nodeid+1)
g2 = [set() for _ in range(nodeid+1)]
vs = set()
cut_edges = set()
for i in range(nodeid+1):
    if i in vs:
        continue
    stack = [i]
    dfs_vs = []
    vs.add(i)
    while stack:
        v = stack.pop()
        dfs_vs.append(v)
        for u, j in G[v]:
            if u in vs:
                continue
            g2[v].add((u, j))
            stack.append(u)
            vs.add(u)
    for v in dfs_vs[::-1]:
        r = d[v]
        for u, j in g2[v]:
            ff = xxs[u]
            if ff:
                cut_edges.add(j)
            r = (r+ff)%2
        xxs[v] = r if v != 0 else 0
    if xxs[i]:
        print(-1)
        break
else:
    print(len(cut_edges))
    print(*sorted(cut_edges))