Problem:


Score : 1000 points

Problem Statement

Ringo has a string S.

He can perform the following N kinds of operations any number of times in any order.

Operation i: For each of the characters from the L_i-th through the R_i-th characters in S, replace it with its succeeding letter in the English alphabet. (That is, replace a with b, replace b with c and so on.) For z, we assume that its succeeding letter is a.

Ringo loves palindromes and wants to turn S into a palindrome.
Determine whether this is possible.

Constraints

1 \leq |S| \leq 10^5

S consists of lowercase English letters.

1 \leq N \leq 10^5

1 \leq L_i \leq R_i \leq |S|

Input

Input is given from Standard Input in the following format:

S
N
L_1 R_1
L_2 R_2
:
L_N R_N

Output

Print YES if it is possible to turn S into a palindrome; print NO if it is impossible.

Sample Input 1

bixzja
2
2 3
3 6

Sample Output 1

YES

For example, if we perform Operation 1, 2 and 1 in this order, S changes as bixzja → bjyzja → bjzakb → bkaakb and becomes a palindrome.

Sample Input 2

abc
1
2 2

Sample Output 2

NO

Sample Input 3

cassert
4
1 2
3 4
1 1
2 2

Sample Output 3

YES



Sample input:
bixzja
2
2 3
3 6


Sample output:
YES

Submission status: Wrong Answer

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()
sys.setrecursionlimit(10**5)
n=len(S)
N=int(input())
k=n//2

def solve(Edge):
    edge=[[] for i in range(k+1)]
    for l,r,i in Edge:
        if l==0 or r==0:
            continue
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

if n%2==0:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        Edge.append((l,r,i))
    solve(Edge)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

S = [ord(x)-ord('a') for x in readline().rstrip()]
N = int(readline())
LR = (tuple(int(x)-1 for x in line.split()) for line in readlines())

LS = len(S)
M = (LS+1)//2

# 左側の区間内の反転に帰着

L_to_R = [[] for _ in range(M+1)]
for L,R in LR:
    if R <= M:
        pass
    elif M<L:
        L,R = LS-1-R,LS-1-L
    elif L+R > LS-1:
        L,R = LS-1-R,L-1
    elif L+R <= LS-1:
        L,R = L,LS-R-2
    if L<=R:
        L_to_R[L].append(R)

bl = True
add = 0
diff_add = [0] * (LS+1)
for L in range(LS//2):
    add += diff_add[L]
    left = S[L]
    right = S[LS-L-1]
    arr = sorted(set(L_to_R[L]))
    if len(arr) == 0:
        if (left + add) % 26 != right:
            bl = False
            break
    else:
        R0 = arr[0]
        for R in arr[1:]:
            L_to_R[R0+1].append(R)
        n = (right-left-add)%26
        add += n
        diff_add[R0+1] -= n

answer = 'YES' if bl else 'NO'
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
            r%=26
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()
sys.setrecursionlimit(10**5)
n=len(S)
N=int(input())
k=n//2



if n%2==0:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")
else:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif l==k:
            R=k-1
            L=n-1-r
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        elif r==k:
            edge[l].append((k,1,i))
            edge[k].append((l,-1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()
sys.setrecursionlimit(10**5)
n=len(S)
N=int(input())
k=n//2



if n%2==0:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")
else:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif l==k:
            R=k-1
            L=n-1-r
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        elif r==k:
            edge[l].append((k,1,i))
            edge[k].append((l,-1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_e

回文をちゃんと定義しよう？
左の文字を何回変化させたら右になるか、をxとする
iを並べた時、対象の部分の和は26(の倍数)でなくてはならない
ただし、xの列が奇数調なら真ん中は0

abba なら
1,0,25

すると、l,rは2点を更新するだけになる
index l-1を+1し、rを-1する(mod26せよ,1-origin)
左右反転した部分の和を配列yとしてもつ(mod26)
すると、配列の2つの部分に+1,-1する操作を好きな回数だけ行って全て
26の倍数にせよという問題になる。

+→-の有向グラフで考える
まず、連結成分ごとに全てのノードの初期値の総和が26の倍数で無いなら不可能
そうでなければ可能(端から合わせていけば絶対つじつまが合うため)
解けたのでは？
あ、ただし、-1 or len(S-1)とリンクしてる連結成分は26の倍数でなくてもよい
1-indexedのほうがいいか？
0 or len(S)とリンクしてる連結成分は26の倍数でなくてもよい

"""
import sys
sys.setrecursionlimit(200000)
alp = "abcdefghijklmnopqrstuvwxyz"
ad = {}
for i in range(26):
    ad[alp[i]] = i

S = input()
x = []

for i in range(len(S)-1):
    x.append((ad[S[i+1]]-ad[S[i]]) % 26)

y = [0]
for j in range((len(x)+1)//2):

    j2 = len(x)-1-j

    if j != j2:
        y.append(x[j]+x[j2])
    else:
        y.append(x[j])

#print (x,y)
N = int(input())

lis = [ [] for i in range(len(y)) ] #連結リスト
for loop in range(N):
    
    l,r = map(int,input().split())
    l -= 1

    l = min( l , len(x)+1-l )
    r = min( r , len(x)+1-r )

    lis[l].append(r)
    lis[r].append(l)

#print (lis)

def dfs(v):
    ret = y[v]
    visit[v] = True
    for nex in lis[v]:
        if not visit[nex]:
            ret += dfs(nex)
    return ret

visit = [False] * len(lis)
ans = "YES"
for i in range(len(lis)):

    if visit[i]:
        continue
    rec = dfs(i)
    if i != 0 and rec % 26 != 0:
        ans = "NO"
        break

print (ans)

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_e

回文をちゃんと定義しよう？
左の文字を何回変化させたら右になるか、をxとする
iを並べた時、対象の部分の和は26(の倍数)でなくてはならない
ただし、xの列が奇数調なら真ん中は0

abba なら
1,0,25

すると、l,rは2点を更新するだけになる
index l-1を+1し、rを-1する(mod26せよ,1-origin)
左右反転した部分の和を配列yとしてもつ(mod26)
すると、配列の2つの部分に+1,-1する操作を好きな回数だけ行って全て
26の倍数にせよという問題になる。

+→-の有向グラフで考える
まず、連結成分ごとに全てのノードの初期値の総和が26の倍数で無いなら不可能
そうでなければ可能(端から合わせていけば絶対つじつまが合うため)
解けたのでは？
あ、ただし、-1 or len(S-1)とリンクしてる連結成分は26の倍数でなくてもよい
1-indexedのほうがいいか？
0 or len(S)とリンクしてる連結成分は26の倍数でなくてもよい

"""
import sys
sys.setrecursionlimit(200000)
alp = "abcdefghijklmnopqrstuvwxyz"
ad = {}
for i in range(26):
    ad[alp[i]] = i

S = input()
x = []

for i in range(len(S)-1):
    x.append((ad[S[i+1]]-ad[S[i]]) % 26)

y = [0]
for j in range((len(x)+1)//2):

    j2 = len(x)-1-j

    if j != j2:
        y.append(x[j]+x[j2])
    else:
        y.append(x[j])

#print (x,y)
N = int(input())

lis = [ [] for i in range(len(y)) ] #連結リスト
for loop in range(N):
    
    l,r = map(int,input().split())
    l -= 1

    l = min( l , len(x)+1-l )
    r = min( r , len(x)+1-r )

    lis[l].append(r)
    lis[r].append(l)

#print (lis)

def dfs(v):
    ret = y[v]
    visit[v] = True
    for nex in lis[v]:
        if not visit[nex]:
            ret += dfs(nex)
    return ret

visit = [False] * len(lis)
ans = "YES"
for i in range(len(lis)):

    if visit[i]:
        continue
    rec = dfs(i)
    if i != 0 and rec % 26 != 0:
        ans = "NO"
        break

print (ans)

Submission status: Runtime Error

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()

input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**5)


n=len(S)
N=int(input())
k=n//2



if n%2==0:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")
else:
    edge=[[] for i in range(k+1)]
    for i in range(N):
        l,r=map(int,input().split())
        l-=1;r-=1;
        if l>k:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif l==k:
            R=k-1
            L=n-1-r
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        elif r==k:
            edge[l].append((k,1,i))
            edge[k].append((l,-1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

Submission status: Runtime Error

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()
sys.setrecursionlimit(10**5)
n=len(S)
N=int(input())
k=n//2

def solve(Edge):
    edge=[[] for i in range(k+1)]
    for l,r,i in Edge:
        if l==0 and r==0:
            continue
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

if n%2==0:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        Edge.append((l,r,i))
    solve(Edge)
else:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        if l==k+1 and r==k+1:
            Edge.append((0,0,i))
        elif l==k+1:
            r-=1
            Edge.append((l,r,i))
        elif r==k+1:
            r-=1
            Edge.append((l,r,i))
        elif l>k+1:
            l-=1;r-=1
            Edge.append((l,r,i))
        elif r>k+1:
            r-=1
            Edge.append((l,r,i))
        else:
            Edge.append((l,r,i))
    solve(Edge)

Submission status: Runtime Error

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()
sys.setrecursionlimit(10**5)
n=len(S)
N=int(input())
k=n//2

def solve(Edge):
    edge=[[] for i in range(k+1)]
    for l,r,i in Edge:
        if l==0 or r==0:
            continue
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

if n%2==0:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        Edge.append((l,r,i))
    solve(Edge)
else:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        if l==r==k+1:
            Edge.append((0,0,i))
        elif l==k+1:
            r-=1
            Edge.append((l,r,i))
        elif r==k+1:
            r-=1
            Edge.append((l,r,i))
        elif l>k+1:
            l-=1;r-=1
            Edge.append((l,r,i))
        elif r>k+1:
            r-=1
            Edge.append((l,r,i))
        else:
            Edge.append((l,r,i))
    solve(Edge)

Submission status: Runtime Error

Solution code:
def solveequation(edge,ans,n,m):
    #edge=[[to,dire,id]...]
    x=[0]*m
    used=[False]*n

    def dfs(v):
        used[v]=True
        r=ans[v]
        for to,dire,id in edge[v]:
            if used[to]:
                continue
            y=dfs(to)
            if dire==-1:
                x[id]=y
            else:
                x[id]=-y
            r+=y
        return r

    for v in range(n):
        if used[v]:
            continue
        y=dfs(v)
        if y%26!=0:
            return False
    return x

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={i:e for e,i in enumerate(alphabetlist)}


import sys

S=input()

input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**5)


n=len(S)
N=int(input())
k=n//2

def solve(Edge):
    edge=[[] for i in range(k+1)]
    for l,r,i in Edge:
        if l==0 or r==0:
            continue
        l-=1;r-=1;
        if l>k-1:
            L=n-1-r
            R=n-1-l
            edge[L].append((R+1,-1,i))
            edge[R+1].append((L,1,i))
        elif r>k-1:
            R=n-1-r
            if R>l:
                edge[l].append((R,1,i))
                edge[R].append((l,-1,i))
            elif l>R:
                edge[l].append((R,-1,i))
                edge[R].append((l,1,i))
        else:
            edge[l].append((r+1,1,i))
            edge[r+1].append((l,-1,i))
    ans=[alpha[S[i]]-alpha[S[-i-1]] for i in range(k)]
    ans+=[0]
    for i in range(k,0,-1):
        ans[i]-=ans[i-1]
    res=solveequation(edge,ans,k+1,N)
    if res:
        print("YES")
    else:
        print("NO")

if n%2==0:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        Edge.append((l,r,i))
    solve(Edge)
else:
    Edge=[]
    for i in range(N):
        l,r=map(int,input().split())
        if l==r==k+1:
            Edge.append((0,0,i))
        elif l==k+1:
            r-=1
            Edge.append((l,r,i))
        elif r==k+1:
            r-=1
            Edge.append((l,r,i))
        elif l>k+1:
            l-=1;r-=1
            Edge.append((l,r,i))
        elif r>k+1:
            r-=1
            Edge.append((l,r,i))
        else:
            Edge.append((l,r,i))
    solve(Edge)