Submission #66732331

---

Source Code Expand

from bisect           import bisect, bisect_left
from collections      import defaultdict,deque,Counter
from copy             import deepcopy
from decimal          import Decimal, ROUND_HALF_UP
from functools        import lru_cache
from heapq            import heapify, heappop, heappush
from itertools        import combinations,permutations,groupby
from pprint           import pprint
from math             import prod, sqrt, perm
from sortedcontainers import SortedSet, SortedList, SortedDict
from string           import ascii_lowercase,ascii_uppercase,digits
from sys              import stdin, setrecursionlimit


class UnionFind():
    #「uf = UnionFind(頂点の数)」で初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x): #uf.find(x)
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y): #uf.union(x, y)
        #要素xが属するグループと要素yが属するグループを併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x): #uf.size(x)
        #要素xが属するグループの要素数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y): #uf.same(x,y)
        #要素x,yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x): #uf.members(x)
        #要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self): #uf.roots()
        #根となっている要素すべてをリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self): #uf.group_count()
        #グループの数を返す
        return len(self.roots())

    def all_group_members(self): #uf.all_group_members()
        #{ルート要素 : [そのグループに含まれる要素のリスト], ...}のdefaultdictを返す
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())



class BinaryTrie:
    def __init__(self, max_query=2*10**5, bitlen=60):
        n = max_query * bitlen
        self.nodes = [-1] * (2 * n)
        self.cnt = [0] * n
        self.id = 0
        self.bitlen = bitlen

    def size(self):
        return self.cnt[0]

    def count(self,x): #xの個数
        pt = 0
        for i in range(self.bitlen-1,-1,-1):
            y = x>>i&1
            if self.nodes[2*pt+y] == -1:
                return 0
            pt = self.nodes[2*pt+y]
        return self.cnt[pt]

    def insert(self,x): #xの挿入
        pt = 0
        for i in range(self.bitlen-1,-1,-1):
            y = x>>i&1
            if self.nodes[2*pt+y] == -1:
                self.id += 1
                self.nodes[2*pt+y] = self.id
            self.cnt[pt] += 1
            pt = self.nodes[2*pt+y]
        self.cnt[pt] += 1


    def erase(self,x): #xの削除、xが存在しないときは何もしない
        if self.count(x) == 0:
            return
        pt = 0
        for i in range(self.bitlen-1,-1,-1):
            y = x>>i&1
            self.cnt[pt] -= 1
            pt = self.nodes[2*pt+y]
        self.cnt[pt] -= 1

    
    def kth_elm(self,x): #昇順x番目の値(1-indexed)
        assert 1 <= x <= self.size()
        pt, ans = 0, 0
        for i in range(self.bitlen-1,-1,-1):
            ans <<= 1
            if self.nodes[2*pt] != -1 and self.cnt[self.nodes[2*pt]] > 0:
                if self.cnt[self.nodes[2*pt]] >= x:
                    pt = self.nodes[2*pt]
                else:
                    x -= self.cnt[self.nodes[2*pt]]
                    pt = self.nodes[2*pt+1]
                    ans += 1
            else:
                pt = self.nodes[2*pt+1]
                ans += 1
        return ans

    def lower_bound(self,x): #x以上の最小要素が昇順何番目か(1-indexed)、x以上の要素がない時はsize+1を返す
        pt, ans = 0, 1
        for i in range(self.bitlen-1,-1,-1):
            if pt == -1: break
            if x>>i&1 and self.nodes[2*pt] != -1:
                ans += self.cnt[self.nodes[2*pt]]
            pt = self.nodes[2*pt+(x>>i&1)]
        return ans




def base_to(num, base): #10進数Numをbase進法に
    res_list = []
    while num:
        res_list.append(str(num%base))
        num //= base
    return res_list[::-1]

def base_from(num, base): #{base}進法の整数Numを10進法に
    return int(str(num), base)

def check_in_grid(height,width,i,j): #(i,j)が height x widthのグリッドの中の点か確認
    return ((0 <= i < height) and (0 <= j < width))

def check_intersection(a,b,c,d, flg_edge=False):#数直線上の線分abと線分cdの共通部分があるかどうかチェック(flg_edgeがTrueなら端点のみの共有を含む)
    if flg_edge:
        return (max(a,c) <= min(b,d))
    else:
        return (max(a,c) < min(b,d))

def clamp(num,smallest,largest): #numがsmallest以下ならsmallestに、largest以上ならlargestに調整
    return max(smallest,min(num,largest))

def count_digit(num): #整数numの桁数
    return len(str(num))

def divisor(x): #整数xの約数をすべて入れたリスト
    divisors = []
    sqrt_x = int(x ** 0.5)
    for i in range(1, sqrt_x + 1):
        if x % i == 0:
            divisors.append(i)
            if i != x // i:
                divisors.append(x // i)
    return divisors

def is_over_180degree(ax,ay,bx,by): #ベクトルa(ax,ay)とベクトルb(bx,by)の角度(aから反時計回りに)が180°より大きければ1、180°ちょうどなら2
    if ax*by - bx*ay < 0:
        return 1
    elif ax*by - bx*ay == 0:
        return 2
    return 0

def is_prime(i): #iが素数かの判定
    if i <= 1:
        return False
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            return False
    return True

def longest_increasing_subsequence(A, INF=10**9): #配列Aの最長増加部分列LISのリスト、計算量O(N*logN)
    dp = [INF for _ in A]
    b = [-1 for _ in A]
    for i in range(len(A)):
        idx = bisect_left(dp, A[i])
        dp[idx] = A[i]
        b[i] = idx + 1
    l = bisect_left(dp, INF)
    seq = [0 for i in range(l)]
    for i in range(len(A)-1, -1, -1):
        if b[i] == l:
            l -= 1
            seq[l] = A[i]
    return seq

def my_round(num, d):#偶数丸めではない四捨五入、dは四捨五入の桁数(ex:0は1の位、2は100の位、-2は0.01の位)
    if d <= 0:
        return Decimal(str(num)).quantize(Decimal(str(10**d)), rounding=ROUND_HALF_UP)
    else:
        p = Decimal(str(num)).quantize(Decimal("1E" + str(d)), rounding=ROUND_HALF_UP)
        return p.quantize(Decimal(1))

def ninety_dig_turn(l): #2次元配列lを時計回りに90度回転
    return list(zip(*l[::-1]))

def pascal_triangle(n): #n段のパスカルの三角形(list, 計算量O(n**2))
    res = []
    for i in range(1,n+1):
        if i == 1:
            tmp = [1]
        elif i == 2:
            tmp = [1,1]
        else:
            tmp = []
            for j in range(i):
                if j == 0 or j == i-1:
                    tmp.append(1)
                else:
                    tmp.append(res[i-2][j-1] + res[i-2][j])
        res.append(tmp)
    return res

def pow_x(x, n): #xの0乗～n乗までのリスト
    List_pow = [1]
    for _ in range(n):
        List_pow.append(x * List_pow[-1])
    return List_pow

def prime_factorize(num): #numを素因数分解したリスト
    factors = []
    while num % 2 == 0:
        factors.append(2)
        num //= 2
    f = 3
    while f * f <= num:
        while num % f == 0:
            factors.append(f)
            num //= f
        f += 2
    if num > 1:
        factors.append(num)
    
    return factors

def run_length_encoding(str_a: str): #連長圧縮、「ある文字がいくつ連続しているか」を順番に集めたリスト
    res = [[key,len(list(group))] for key,group in groupby(str_a)]
    return res

def Sieve_of_Eratosthenes(num): #num以下の数へのエラトステネスの篩(sortedlist)、計算量O(n*loglogn)
    res = [True] * (num + 1)
    res[0] = res[1] = False
    for i in range(2, int(num**0.5) + 1):
        if res[i]:
            for j in range(i*i, num + 1, i):
                res[j] = False
    return [i for i in range(num + 1) if res[i]]

def triangle_area(ax,ay,bx,by,cx,cy):#a(ax,ay),b(bx,by),c(cx,cy)の3点からなる三角形の面積
    return abs((bx-ax)*(cy-ay) - (cx-ax)*(by-ay)) / 2

#入力の高速化
readline = stdin.readline

if 1: #入力系
    def si(): return input()
    #---1つの文字列の受け取り
    def ii(): return int(input())
    #---1つの整数の受け取り
    def mii(n = 0): return map(lambda x: int(x)+n, readline().split(" "))
    #---スペースで区切られた複数の整数をそれぞれ+nして受け取り
    def lmii(n = 0): return list(map(lambda x: int(x)+n, readline().split(" ")))
    #---スペースで区切られた複数の整数をそれぞれ+nしてリストで受け取り
    def msi(): return readline().strip()
    #---スペースなしの連続した文字列を1文字ずつ受け取り
    def msis(): return readline().strip().split()
    #---スペースで区切られた複数の文字列の受け取り
    def lmsi(): return list(readline().strip())
    #---スペースなしの連続した文字列を1文字ずつリストで受け取り
    def lmsis(): return list(readline().strip().split())
    #---スペースで区切られた複数の文字列をリストで受け取り

def pryn(ok): return print("Yes" if ok else "No")
#---変数"ok"がTrueなら"Yes"、Falseなら"No"を出力

#再帰関数の呼び出し回数上限変更
setrecursionlimit(10**7)

#import string
Upper = list(ascii_uppercase) #大文字アルファベットのリスト(["A", "B", "C", ....])
Lower = list(ascii_lowercase) #小文字アルファベットのリスト(["a", "b", "c", ....])
Numbers = list(digits)        #1桁の数字のリスト(["0","1","2", ....])(各要素はstr)

#座標の移動　12時方向から時計回り8方向
dir8 = [(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1)]
#4方向はこっち　newx=nx+dir4[d], newy=ny+dir4[d+1]
dir4 = [0,1,0,-1,0]

INF = float('inf')
MOD1 = 998244353
MOD2 = 10**9+7

#latestupdate 20250131
#-----------------------------------------
#-----------------------------------------

n,q = mii()
p = [i for i in range(1,n+1)]
c = 0
for _ in range(q):
    t = lmii()
    if t[0] == 1:
        u,v = t[1:]
        p[(u-1-c)%n] = v
    elif t[0] == 2:
        print(p[(t[1]-1-c)%n])
    else:
        c -= t[1]
        c %= n

Submission Info

Judge Result