Biased Dice

source: ACM International Collegiate Programming Contest, Japan Domestic 2012

raw_problem:
Biased Dice

Professor Random, known for his research on randomized algorithms, is now conducting an experiment on biased dice.  His experiment consists of dropping a number of dice onto a plane, one after another from a fixed position above the plane.  The dice fall onto the plane or dice already there, without rotating, and may roll and fall according to their property.  Then he observes and records the status of the stack formed on the plane, specifically, how many times each number appears on the faces visible from above. All the dice have the same size and their face numbering is identical, which we show in Figure C-1.

Figure C-1: Numbering of a die

The dice have very special properties, as in the following.

(1) Ordinary dice can roll in four directions, but the dice used in this experiment never roll in the directions of faces 1, 2 and 3; they can only roll in the directions of faces 4, 5 and 6.  In the situation shown in Figure C-2, our die can only roll to one of two directions.

Figure C-2: An ordinary die and a biased die

(2) The die can only roll when it will fall down after rolling, as shown in Figure C-3.  When multiple possibilities exist, the die rolls towards the face with the largest number among those directions it can roll to.

Figure C-3: A die can roll only when it can fall

(3) When a die rolls, it rolls exactly 90 degrees, and then falls straight down until its bottom face touches another die or the plane, as in the case [B] or [C] of Figure C-4.

(4) After rolling and falling, the die repeatedly does so according to the rules (1) to (3) above.

Figure C-4: Example stacking of biased dice

For example, when we drop four dice all in the same orientation, 6 at the top and 4 at the front, then a stack will be formed as shown in Figure C-4.

Figure C-5: Example records

After forming the stack, we count the numbers of faces with 1 through 6 visible from above and record them.  For example, in the left case of Figure C-5, the record will be "0 2 1 0 0 0", and in the right case, "0 1 1 0 0 1".

Input

The input consists of several datasets each in the following format.

n

t1  f1

t2  f2

...

tn  fn

Here, n (1 ≤ n ≤ 100) is an integer and is the number of the dice to be dropped.  ti and fi (1 ≤ ti, fi ≤ 6) are two integers separated by a space and represent the numbers on the top and the front faces of the i-th die, when it is released, respectively.

The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output six integers separated by a space. The integers represent the numbers of faces with 1 through 6 correspondingly, visible from above. There may not be any other characters in the output.

Sample Input

4
6 4
6 4
6 4
6 4
2
5 3
5 3
8
4 2
4 2
4 2
4 2
4 2
4 2
4 2
4 2
6
4 6
1 5
2 3
5 3
2 4
4 2
0

Output for the Sample Input

0 1 1 0 0 1
1 0 0 0 1 0
1 2 2 1 0 0
2 3 0 0 0 0

solutions: ["from collections import defaultdict\n\ndef getdice(a, b):\n\tta, tb = a, b\n\twhile ta >= 4 or tb >= 4:\n\t\tta, tb = tb, 7 - ta\n\tx = 6 - ta - tb\n\tif (tb - ta) % 3 == 2:\n\t\tx = 7 - x\n\treturn [ a, b, x, 7 - b, 7 - x, 7 - a ]\n\ndx = [ 1, 0, -1, 0 ]\ndy = [ 0, 1, 0, -1 ]\ntrans = [\n\t[ 3, 0, 2, 5, 4, 1 ],\n\t[ 4, 1, 0, 3, 5, 2 ],\n\t[ 1, 5, 2, 0, 4, 3 ],\n\t[ 2, 1, 5, 3, 0, 4 ]\n]\n\nwhile True:\n\tn = int(input())\n\tif n == 0:\n\t\tbreak\n\tcnt = defaultdict(int)\n\ttop = {}\n\tfor i in range(n):\n\t\ta, b = map(int, input().split())\n\t\tx, y = 0, 0\n\t\td = getdice(a, b)\n\t\twhile True:\n\t\t\tdir, opt = -1, 3\n\t\t\tfor i in range(4):\n\t\t\t\tif d[i + 1] > opt and cnt[(x + dx[i], y + dy[i])] < cnt[(x, y)]:\n\t\t\t\t\tdir, opt = i, d[i + 1]\n\t\t\tif dir == -1:\n\t\t\t\tbreak\n\t\t\tx, y = x + dx[dir], y + dy[dir]\n\t\t\td = [ d[trans[dir][i]] for i in range(6) ]\n\t\tcnt[(x, y)] += 1\n\t\ttop[(x, y)] = d[0]\n\tprint(*[ list(top.values()).count(i) for i in range(1, 7)])\n", "right_dic = {(1, 3):5, (1, 5):4, (1, 4):2, (1, 2):3,\n             (2, 1):4, (2, 4):6, (2, 6):3, (2, 3):1,\n             (3, 1):2, (3, 2):6, (3, 6):5, (3, 5):1,\n             (4, 1):5, (4, 5):6, (4, 6):2, (4, 2):1,\n             (5, 1):3, (5, 3):6, (5, 6):4, (5, 4):1,\n             (6, 2):4, (6, 4):5, (6, 5):3, (6, 3):2}\n\n\nclass Dice:\n    def __init__(self, top, front):\n        self.top = top\n        self.front = front\n        self.right = right_dic[(top, front)]\n        self.under = 7 - self.top\n        self.back= 7 - self.front\n        self.left = 7 - self.right\n\n    def spin_right(self):\n        self.top, self.right, self.under, self.left = self.left, self.top, self.right, self.under\n\n    def spin_left(self):\n        self.top, self.right, self.under, self.left = self.right, self.under, self.left, self.top\n\n    def spin_front(self):\n        self.top, self.front, self.under, self.back = self.back, self.top, self.front, self.under\n\n    def spin_back(self):\n        self.top, self.front, self.under, self.back = self.front, self.under, self.back, self.top\n\n\nwhile True:\n    n = int(input())\n    if n == 0:\n        break\n\n    mp = [[0] * (n * 2 + 2) for _ in range(n * 2 + 2)]\n    show = [[0] * (n * 2 + 2) for _ in range(n * 2 + 2)]\n    counter = [0] * 7\n    STOP, FRONT, RIGHT, BACK, LEFT = 0, 1, 2, 3, 4\n    for _ in range(n):\n        x, y = n + 1, n + 1\n        top, front = map(int, input().split())\n        dice = Dice(top, front)\n        while True:\n            rec = 3\n            direct = STOP\n            if mp[y + 1][x] < mp[y][x] and dice.front > rec:\n                rec = dice.front\n                direct = FRONT\n            if mp[y][x + 1] < mp[y][x] and dice.right > rec:\n                rec = dice.right\n                direct = RIGHT\n            if mp[y - 1][x] < mp[y][x] and dice.back > rec:\n                rec = dice.back\n                direct = BACK\n            if mp[y][x - 1] < mp[y][x] and dice.left > rec:\n                rec = dice.left\n                direct = LEFT\n\n            if direct == STOP:\n                mp[y][x] += 1\n                counter[show[y][x]] -= 1\n                counter[dice.top] += 1\n                show[y][x] = dice.top\n                break\n            elif direct == FRONT:\n                dice.spin_front()\n                y += 1\n            elif direct == RIGHT:\n                dice.spin_right()\n                x += 1\n            elif direct == BACK:\n                dice.spin_back()\n                y -= 1\n            elif direct == LEFT:\n                dice.spin_left()\n                x -= 1\n\n    print(*counter[1:])\n\n", "#!usr/bin/env python3\nfrom collections import defaultdict,deque\nfrom heapq import heappush, heappop\nimport sys\nimport math\nimport bisect\nimport random\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef I(): return int(sys.stdin.readline())\ndef LS():return [list(x) for x in sys.stdin.readline().split()]\ndef S(): return list(sys.stdin.readline())[:-1]\ndef IR(n):\n    return [I() for i in range(n)]\ndef LIR(n):\n    return [LI() for i in range(n)]\ndef SR(n):\n    return [S() for i in range(n)]\ndef LSR(n):\n    return [LS() for i in range(n)]\n\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\n#2005_c\n\"\"\"\nn = int(input())\nk = list(\"mcxi\")\nfor i in range(n):\n    d = {\"m\":0,\"c\":0,\"x\":0,\"i\":0}\n    a,b  = input().split()\n    a = list(a)\n    b = list(b)\n    a.insert(0,1)\n    b.insert(0,1)\n    for j in range(1,len(a)):\n        if a[j] in k:\n            if a[j-1] in k:\n                d[a[j]] += 1\n            else:\n                d[a[j]] += int(a[j-1])\n    for j in range(1,len(b))[::-1]:\n        if b[j] in k:\n            if b[j-1] in k:\n                d[b[j]] += 1\n            else:\n                d[b[j]] += int(b[j-1])\n            if d[b[j]] >= 10:\n                l = b[j]\n                while d[l] >= 10:\n                    d[l] -= 10\n                    l = k[k.index(l)-1]\n                    d[l] += 1\n    for j in k:\n        if d[j]:\n            if d[j] == 1:\n                print(j,end = \"\")\n            else:\n                print(str(d[j])+j,end = \"\")\n    print()\n\"\"\"\n\n#2017_c\n\"\"\"\nwhile 1:\n    h, w = map(int, input().split())\n    if h == w == 0:\n        break\n    s = [list(map(int, input().split())) for i in range(h)]\n\n    ans = 0\n    for u in range(h):\n        for d in range(u+2,h):\n            for l in range(w):\n                for r in range(l+2,w):\n                    m = float(\"inf\")\n                    for i in range(u,d+1):\n                        m = min(m,s[i][l],s[i][r])\n                    for i in range(l,r+1):\n                        m = min(m,s[u][i],s[d][i])\n                    f = 1\n                    su = 0\n                    for i in range(u+1,d):\n                        for j in range(l+1,r):\n                            su += (m-s[i][j])\n                            if s[i][j] >= m:\n                                f = 0\n                                break\n                        if not f:\n                            break\n                    if f:\n                        ans = max(ans,su)\n    print(ans)\n\"\"\"\n\n#2016_c\n\"\"\"\nwhile 1:\n    m,n = map(int, input().split())\n    if m == n == 0:\n        break\n    ma = 7368791\n    d = [0]*(ma+1)\n    z = m\n    for i in range(n):\n        while d[z]:\n            z += 1\n        j = z\n        while j <= ma:\n            d[j] = 1\n            j += z\n    for j in range(z,ma+1):\n        if not d[j]:\n            print(j)\n            break\n\"\"\"\n\n#2018_c\n\"\"\"\ndef factorize(n):\n    if n < 4:\n        return [1,n]\n    i = 2\n    l = [1]\n    while i**2 <= n:\n        if n%i == 0:\n            l.append(i)\n            if n//i != i:\n                l.append(n//i)\n        i += 1\n    l.append(n)\n    l.sort()\n    return l\nwhile 1:\n    b = int(input())\n    if b == 0:\n        break\n    f = factorize(2*b)\n    for n in f[::-1]:\n        a = 1-n+(2*b)//n\n        if a >= 1 and a%2 == 0:\n            print(a//2,n)\n            break\n\"\"\"\n\n#2010_c\n\"\"\"\nimport sys\ndp = [100]*1000000\ndp_2 = [100]*1000000\ndp[0] = 0\ndp_2[0] = 0\nfor i in range(1,181):\n    s = i*(i+1)*(i+2)//6\n    for j in range(s,1000000):\n        if dp[j-s]+1 < dp[j]:\n            dp[j] = dp[j-s]+1\n    if s%2:\n        for j in range(s,1000000):\n            if dp_2[j-s]+1 < dp_2[j]:\n                dp_2[j] = dp_2[j-s]+1\nwhile 1:\n    m = int(sys.stdin.readline())\n    if m == 0:\n        break\n    print(dp[m],dp_2[m])\n\"\"\"\n\n#2015_c\n\"\"\"\nfrom collections import deque\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    s = [input() for i in range(n)]\n    d = [s[i].count(\".\") for i in range(n)]\n    m = max(d)\n    c = [s[i][-1] for i in range(n)]\n    q = deque()\n    for i in range(1,m+1)[::-1]:\n        j = 0\n        while j < n:\n            for k in range(j,n):\n                if d[k] == i:break\n            else:\n                break\n            j = k\n            op = c[j-1]\n            while j < n and d[j] == i:\n                q.append(j)\n                j += 1\n            j = k\n            if op == \"+\":\n                k = 0\n                while q:\n                    x = q.pop()\n                    k += int(c[x])\n                    c.pop(x)\n                    d.pop(x)\n                    n -= 1\n            else:\n                k = 1\n                while q:\n                    x = q.pop()\n                    k *= int(c[x])\n                    c.pop(x)\n                    d.pop(x)\n                    n -= 1\n            c[j-1] = k\n    print(c[0])\n\"\"\"\n\n#2013_c\n\"\"\"\nfrom collections import defaultdict\n\ndef parse_expr(s,i):\n    i += 1\n    if s[i] == \"[\":\n        q = []\n        while s[i] != \"]\":\n            e,i = parse_expr(s,i)\n            q.append(e)\n        return (calc(q),i+1)\n    else:\n        n,i = parse_num(s,i)\n        return (calc([n]),i+1)\n\ndef parse_num(s,i):\n    m = int(s[i])\n    i += 1\n    while f_num[s[i]]:\n        m *= 10\n        m += int(s[i])\n        i += 1\n    return (m,i)\n\ndef calc(q):\n    if len(q) == 1:\n        return (q[0]+1)//2\n    q.sort()\n    return sum(q[:len(q)//2+1])\n\nf_num = defaultdict(lambda : 0)\nfor i in range(10):\n    f_num[str(i)] = 1\n\nn = int(input())\nfor i in range(n):\n    s = input()\n    print(parse_expr(s,0)[0])\n\"\"\"\n\n#2003_C\n\"\"\"\nwhile 1:\n    w,h = LI()\n    if w == h == 0:\n        break\n    s = SR(h)\n    dp = [[0]*w for i in range(h)]\n    for y in range(h):\n        for x in range(w):\n            if s[y][x].isdecimal():\n                dp[y][x] = max(dp[y-1][x],dp[y][x-1])*10+int(s[y][x])\n    ans = 0\n    for i in dp:\n        ans = max(ans,max(i))\n    print(ans)\n\"\"\"\n#2008_C\n\"\"\"def parse_formula(s,i):\n    if s[i] == \"-\":\n        i += 1\n        e,i = parse_formula(s,i)\n        return 2-e,i\n    elif s[i] == \"(\":\n        i += 1\n        e1,i = parse_formula(s,i)\n        op = s[i]\n        i += 1\n        e2,i = parse_formula(s,i)\n        i += 1\n        return calc(op,e1,e2),i\n    else:\n        return int(s[i]),i+1\n\ndef calc(op,a,b):\n    if op == \"*\":\n        return min(a,b)\n    else:\n        return max(a,b)\n\nwhile 1:\n    s = S()\n    if s[0] == \".\":\n        break\n    t = []\n    f = defaultdict(int)\n    for p in range(3):\n        f[\"P\"] = p\n        for q in range(3):\n            f[\"Q\"] = q\n            for r in range(3):\n                f[\"R\"] = r\n                t.append([f[s[i]] if s[i] in \"PQR\" else s[i] for i in range(len(s))])\n    ans = 0\n    for s in t:\n        if parse_formula(s,0)[0] == 2:\n            ans += 1\n    print(ans)\n\"\"\"\n#2011_C\n\"\"\"\nd = [(1,0),(-1,0),(0,1),(0,-1)]\ndef dfs(dep,s):\n    global ans\n    if dep == 5:\n        b = bfs(s)\n        m = 0\n        for i in b:\n            m += sum(i)\n        ans = max(ans, m)\n    else:\n        if dep < 4:\n            for i in range(6):\n                b = bfs(s)\n                dfs(dep+1,[[i+1 if b[y][x] else s[y][x] for x in range(w)] for y in range(h)])\n        else:\n            b = bfs(s)\n            dfs(dep+1,[[c if b[y][x] else s[y][x] for x in range(w)] for y in range(h)])\n\ndef bfs(s):\n    b = [[0]*w for i in range(h)]\n    b[0][0] = 1\n    q = deque([(0,0)])\n    while q:\n        y,x = q.popleft()\n        for dy,dx in d:\n            y_ = y+dy\n            x_ = x+dx\n            if 0 <= y_ < h and 0 <= x_ < w:\n                if not b[y_][x_] and s[y_][x_] == s[0][0]:\n                    b[y_][x_] = 1\n                    q.append((y_,x_))\n    return b\n\nwhile 1:\n    h,w,c = LI()\n    if h == 0:\n        break\n    s = LIR(h)\n    ans = 0\n    dfs(0,s)\n    print(ans)\n\"\"\"\n#2012_C\ndef make_dice(t,f):\n    if t == 1:\n        if f == 2:\n            return [t,f,3,7-f,4,7-t]\n        if f == 3:\n            return [t,f,5,7-f,2,7-t]\n        if f == 5:\n            return [t,f,4,7-f,3,7-t]\n        if f == 4:\n            return [t,f,2,7-f,5,7-t]\n    if t == 2:\n        if f == 1:\n            return [t,f,4,7-f,3,7-t]\n        if f == 4:\n            return [t,f,6,7-f,1,7-t]\n        if f == 6:\n            return [t,f,3,7-f,4,7-t]\n        if f == 3:\n            return [t,f,1,7-f,6,7-t]\n    if t == 3:\n        if f == 1:\n            return [t,f,2,7-f,5,7-t]\n        if f == 2:\n            return [t,f,6,7-f,1,7-t]\n        if f == 6:\n            return [t,f,5,7-f,2,7-t]\n        if f == 5:\n            return [t,f,1,7-f,6,7-t]\n    if t == 4:\n        if f == 1:\n            return [t,f,5,7-f,2,7-t]\n        if f == 5:\n            return [t,f,6,7-f,1,7-t]\n        if f == 6:\n            return [t,f,2,7-f,5,7-t]\n        if f == 2:\n            return [t,f,1,7-f,6,7-t]\n    if t == 5:\n        if f == 1:\n            return [t,f,3,7-f,4,7-t]\n        if f == 3:\n            return [t,f,6,7-f,1,7-t]\n        if f == 6:\n            return [t,f,4,7-f,3,7-t]\n        if f == 4:\n            return [t,f,1,7-f,6,7-t]\n    if t == 6:\n        if f == 2:\n            return [t,f,4,7-f,3,7-t]\n        if f == 4:\n            return [t,f,5,7-f,2,7-t]\n        if f == 5:\n            return [t,f,3,7-f,4,7-t]\n        if f == 3:\n            return [t,f,2,7-f,5,7-t]\ndy = [0,-1,0,1,0,0]\ndx = [0,0,1,0,-1,0]\ndef Set(s,dice):\n    z,y,x = fall(s,dice,99,99)\n    dir = check(s,z,y,x,dice)\n    while dir:\n        s[z][y][x] = 0\n        dice = rotate(dice,dir)\n        z,y,x = fall(s,dice,y+dy[dir],x+dx[dir])\n        dir = check(s,z,y,x,dice)\n\ndef fall(s,dice,y,x):\n    for z in range(100):\n        if s[z][y][x] == 0:\n            s[z][y][x] = dice[0]\n            return z,y,x\n\ndef check(s,z,y,x,dice):\n    if z == 0:\n        return 0\n    for c in (6,5,4):\n        dir = dice.index(c)\n        if s[z][y+dy[dir]][x+dx[dir]] == 0 and s[z-1][y+dy[dir]][x+dx[dir]] == 0 :\n            return dir\n    return 0\n\ndef rotate(dice,dir):\n    if dir == 1:\n        return [dice[3],dice[0],dice[2],dice[5],dice[4],dice[1]]\n    if dir == 2:\n        return [dice[4],dice[1],dice[0],dice[3],dice[5],dice[2]]\n    if dir == 3:\n        return [dice[1],dice[5],dice[2],dice[0],dice[4],dice[3]]\n    else:\n        return [dice[2],dice[1],dice[5],dice[3],dice[0],dice[4]]\n\nwhile 1:\n    n = I()\n    if n == 0:\n        break\n    s = [[[0]*200 for i in range(200)] for j in range(100)]\n    for i in range(n):\n        t,f = LI()\n        dice = make_dice(t,f)\n        Set(s,dice)\n    d = {0:0,1:0,2:0,3:0,4:0,5:0,6:0}\n    for y in range(200):\n        for x in range(200):\n            for z in range(100):\n                if s[z][y][x] == 0:\n                    break\n            d[s[z-1][y][x]] += 1\n\n    for i in range(1,6):\n        print(d[i],end = \" \")\n    print(d[6])\n\n", "class Dice:\n    def __init__(self, top, front):\n        self.num = [-1] * 6\n        self.num[0] = top\n        self.num[2] = front\n        self.num[3] = 7 - front\n        self.num[5] = 7 - top\n        \n        if (top, front) in [(4, 5), (5, 3), (3, 2), (2, 4)]: self.num[1] = 1\n        elif (top, front) in [(1, 3), (3, 6), (6, 4), (4, 1)]: self.num[1] = 2\n        elif (top, front) in [(1, 5), (5, 6), (6, 2), (2, 1)]: self.num[1] = 3\n        elif (top, front) in [(1, 2), (2, 6), (6, 5), (5, 1)]: self.num[1] = 4\n        elif (top, front) in [(1, 4), (4, 6), (6, 3), (3, 1)]: self.num[1] = 5\n        else: self.num[1] = 6\n        self.num[4] = 7 - self.num[1]\n        \n    def rotate_r(self):\n        num = self.num.copy()\n        num[0] = self.num[1]\n        num[1] = self.num[5]\n        num[5] = self.num[4]\n        num[4] = self.num[0]\n        self.num = num.copy()\n    \n    def rotate_l(self):\n        for _ in range(3):\n            self.rotate_r()\n    \n    def rotate_f(self):\n        num = self.num.copy()\n        num[0] = self.num[3]\n        num[3] = self.num[5]\n        num[5] = self.num[2]\n        num[2] = self.num[0]\n        self.num = num.copy()\n        \n    def rotate_b(self):\n        for _ in range(3):\n            self.rotate_f()\n    \n    def get(self, i):\n        return self.num[i]\n\nwhile 1:\n    n = int(input())\n    if n == 0:\n        break\n    \n    top = [[0] * 120 for _ in range(120)]\n    cnt = [[0] * 120 for _ in range(120)]\n    for _ in range(n):\n        t, f = map(int, input().split())\n        dice = Dice(t, f)\n        rot = [dice.rotate_r, dice.rotate_f, dice.rotate_l, dice.rotate_b]\n        pos = [4, 2, 1, 3]\n        di = [1, 0, -1, 0]\n        dj = [0, -1, 0, 1]\n        i = j = 0\n        while 1:\n            max_ = 0\n            ind = -1\n            for k in range(4):\n                if cnt[i + di[k]][j + dj[k]] >= cnt[i][j]:\n                    continue\n                x = dice.get(pos[k])\n                if x > max(3, max_):\n                    max_ = x\n                    ind = k\n            if max_ == 0:\n                break\n            else:\n                i += di[ind]\n                j += dj[ind]\n                rot[ind]()\n        cnt[i][j] += 1\n        top[i][j] = dice.get(0)\n    \n    ans = [0] * 7\n    for i in range(120):\n        for j in range(120):\n            ans[top[i][j]] += 1\n    print(*ans[1:])\n                \n        \n        \n        \n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**10\nmod = 10**9+7\ndd = [(-1,0),(0,1),(1,0),(0,-1)]\nddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]\n\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\n\nclass Dice():\n    def __init__(self, top, front):\n        # [top, front, bottom, rear, right, left]\n        self.A = [top, front, 7 - top, 7 - front]\n        for i in range(4):\n            t = (self.A[i-1], self.A[i])\n            if t == (6, 4):\n                self.A += [5, 2]\n            elif t == (4, 6):\n                self.A += [2, 5]\n            elif t == (6, 5):\n                self.A += [3, 4]\n            elif t == (6, 2):\n                self.A += [4, 3]\n            elif t == (5, 4):\n                self.A += [1, 6]\n            elif t == (5, 3):\n                self.A += [6, 1]\n            else:\n                continue\n            break\n\n    def top(self):\n        return self.A[0]\n\n    def front(self):\n        return self.A[1]\n\n    def bottom(self):\n        return self.A[2]\n\n    def rear(self):\n        return self.A[3]\n\n    def right(self):\n        return self.A[4]\n\n    def left(self):\n        return self.A[5]\n\n    # di: 0 == front, 1 == rear, 2 == right, 3 == left\n    def rotate(self, di):\n        a = self.A\n        if di == 0:\n            self.A = [a[3], a[0], a[1], a[2], a[4], a[5]]\n        elif di == 1:\n            self.A = [a[1], a[2], a[3], a[0], a[4], a[5]]\n        elif di == 2:\n            self.A = [a[5], a[1], a[4], a[3], a[0], a[2]]\n        elif di == 3:\n            self.A = [a[4], a[1], a[5], a[3], a[2], a[0]]\n\ndef main():\n    rr = []\n\n    while True:\n        n = I()\n        if n == 0:\n            break\n\n        a = [LI() for _ in range(n)]\n        rb = collections.defaultdict(int)\n        b = collections.defaultdict(int)\n        for t,f in a:\n            ki = 0\n            kj = 0\n            d = Dice(t,f)\n            f = True\n            while f:\n                f = False\n                bt = b[(ki,kj)]\n                for i in range(6,3,-1):\n                    if d.front() == i and bt > b[(ki-1,kj)]:\n                        f = True\n                        d.rotate(0)\n                        ki -= 1\n                        break\n                    if d.rear() == i and bt > b[(ki+1,kj)]:\n                        f = True\n                        d.rotate(1)\n                        ki += 1\n                        break\n                    if d.right() == i and bt > b[(ki,kj+1)]:\n                        f = True\n                        d.rotate(2)\n                        kj += 1\n                        break\n                    if d.left() == i and bt > b[(ki,kj-1)]:\n                        f = True\n                        d.rotate(3)\n                        kj -= 1\n                        break\n            b[(ki,kj)] += 1\n            rb[(ki,kj)] = d.top()\n\n        r = [0] * 6\n        for v in rb.values():\n            if v == 0:\n                continue\n            r[v-1] += 1\n\n        rr.append(' '.join(map(str,r)))\n\n    return '\\n'.join(map(str, rr))\n\n\n\nprint(main())\n\n", "dice = [(3,5,4,2),(1,4,6,3),(1,2,6,5),(1,5,6,2),(1,3,6,4),(2,4,5,3)] # 1\u304b\u30896\u304c\u4e0a\u9762\u3067\u3042\u308b\u3068\u304d\u306b\u30b5\u30a4\u30b3\u30ed\u306e\u5074\u9762\u306b\u4e26\u3076\u6570\u5b57\u3092\u53cd\u6642\u8a08\u56de\u308a\u306e\u9806\u306b\u8868\u3057\u305f\u914d\u5217dice\u3092\u4f5c\u6210\nwhile True: # break\u3059\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3057\n    n = int(input()) # \u843d\u3068\u3059\u30b5\u30a4\u30b3\u30ed\u306e\u500b\u6570n\u3092\u5165\u529b\n    if not n: # n\u304c0\u3067\u3042\u308b\u5834\u5408\n        break # \u89e3\u7b54\u7d42\u4e86\n    height = [[0]*5 for i in range(5)] # \u5404\u4f4d\u7f6e\u306b\u7a4d\u307e\u308c\u3066\u3044\u308b\u30b5\u30a4\u30b3\u30ed\u306e\u500b\u6570\u3092\u8868\u3059\u914d\u5217height\u3092\u4f5c\u6210\n    top_num = [[-1]*5 for i in range(5)] # \u5404\u4f4d\u7f6e\u306b\u7a4d\u307e\u308c\u3066\u3044\u308b\u30b5\u30a4\u30b3\u30ed\u306e\u3046\u3061, \u6700\u3082\u4e0a\u306b\u3042\u308b\u3082\u306e\u306e\u4e0a\u9762\u306b\u66f8\u304b\u308c\u3066\u3044\u308b\u6570\u3092\u8868\u3059\u914d\u5217top_num\u3092\u4f5c\u6210\n    move = [(0,1),(1,0),(0,-1),(-1,0)] # \u30b5\u30a4\u30b3\u30ed\u306e\u8ee2\u304c\u3059\u65b9\u5411\u3092\u8868\u3059\u914d\u5217move\u3092\u4f5c\u6210\n    for _ in range(n): # n\u56de\u7e70\u308a\u8fd4\u3057\n        t,f = map(int,input().split()) # \u4e0a\u9762\u306b\u66f8\u304b\u308c\u3066\u3044\u308b\u6570t, \u524d\u9762\u306b\u66f8\u304b\u308c\u3066\u3044\u308b\u6570f\u3092\u5165\u529b\n        ni = 2; nj = 2 # \u30b5\u30a4\u30b3\u30ed\u304c\u843d\u3068\u3055\u308c\u305f\u5730\u70b9\u3092 (2,2) \u3068\u3059\u308b\n        while True: # break\u3059\u308b\u307e\u3067\u7e70\u308a\u8fd4\u3057\n            f_idx = dice[t-1].index(f) # dice[t-1]\u306b\u304a\u3051\u308bf\u306eindex\u3092f_idx\u3068\u3059\u308b\n            for j in range(6,3,-1): # 6\u304b\u30894\u307e\u3067\u7e70\u308a\u8fd4\u3057\n                if j in dice[t-1]: # j\u304cdice[t-1]\u306b\u542b\u307e\u308c\u308b\u5834\u5408\n                    j_idx = dice[t-1].index(j) # dice[t-1]\u306b\u304a\u3051\u308bj\u306eindex\u3092j_idx\u3068\u3059\u308b\n                    di,dj = move[(j_idx - f_idx) % 4] # move\u306e (j_idx - f_idx)%4 \u756a\u76ee\u306e\u8981\u7d20\u3092di,dj\u3068\u3059\u308b\n                    if height[ni+di][nj+dj] < height[ni][nj]: # height[ni+di][nj+dj]\u304cheight[ni][nj]\u3088\u308a\u3082\u5c0f\u3055\u3044\u5834\u5408(j\u304c\u66f8\u304b\u308c\u3066\u3044\u308b\u65b9\u5411\u3078\u8ee2\u304c\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u5834\u5408)\n                        ni = ni+di; nj = nj+dj # ni\u3092ni+di\u306b, nj\u3092nj+dj\u306b\u5909\u66f4\n                        if dj == 1: # dj\u304c1\u3067\u3042\u308b\u5834\u5408(\u524d\u9762\u306e\u65b9\u5411\u306b\u8ee2\u304c\u3059\u5834\u5408)\n                            f = t # f\u3092t\u306b\u5909\u66f4\n                        if dj == -1: # dj\u304c-1\u3067\u3042\u308b\u5834\u5408(\u80cc\u9762\u306e\u65b9\u5411\u306b\u8ee2\u304c\u3059\u5834\u5408)\n                            f = 7 - t # f\u30927-t\u306b\u5909\u66f4\n                        t = 7 - j # t\u30927-j\u306b\u5909\u66f4\n                        break # \u30eb\u30fc\u30d7\u7d42\u4e86\n            else: # break\u3055\u308c\u306a\u304b\u3063\u305f\u5834\u5408(\u8ee2\u304c\u3059\u3053\u3068\u304c\u3067\u304d\u306a\u304b\u3063\u305f\u5834\u5408)\n                height[ni][nj] += 1 # height[ni][nj]\u306b1\u52a0\u7b97\n                top_num[ni][nj] = t # top_num[ni][nj]\u3092t\u306b\u5909\u66f4\n                break # \u30eb\u30fc\u30d7\u7d42\u4e86\n    ans = [0]*6 # \u5404\u9762\u304c\u4e0a\u304b\u3089\u4f55\u500b\u898b\u3048\u308b\u304b\u3092\u8868\u3059\u914d\u5217ans\u3092\u4f5c\u6210\n    for i in range(5): # 0\u304b\u30894\u307e\u3067\u7e70\u308a\u8fd4\u3057\n        for j in range(5): # 0\u304b\u30894\u307e\u3067\u7e70\u308a\u8fd4\u3057\n            if top_num[i][j] != -1: # top_num[i][j]\u304c-1\u3067\u306a\u3044\u5834\u5408(1\u500b\u4ee5\u4e0a\u30b5\u30a4\u30b3\u30ed\u304c\u7a4d\u307e\u308c\u3066\u3044\u308b\u5834\u5408) \n                ans[top_num[i][j]-1] += 1 # ans[top_num[i][j]-1] \u306b1\u52a0\u7b97\n    print(*ans) # ans\u3092\u51fa\u529b\n", "def get_num(top):  # \u8ee2\u304c\u3059\u756a\u53f7\u306e\u5019\u88dc\u3092\u6c7a\u3081\u308b\n    if top == 1:\n        return [5, 4]\n    elif top == 2:\n        return [6, 4]\n    elif top == 3:\n        return [6, 5]\n    elif top == 4:\n        return [6, 5]\n    elif top == 5:\n        return [6, 4]\n    elif top == 6:\n        return [5, 4]\n\n\ndef get_dir(num, front, top):  # \u8ee2\u304c\u308b\u5411\u304d\u3092\u6c7a\u3081\u308b\n    if num == front:\n        return [\"F\", num]\n    elif num == 7 - front:\n        return [\"B\", num]\n    # print(num, front)\n    if num == 4:\n        if (front == 1 and top == 5) or (front == 5 and top == 6) or (front == 6 and top == 2) or (front == 2 and top == 1):\n            return [\"L\", num]\n        elif (front == 5 and top == 1) or (front == 6 and top == 5) or (front == 2 and top == 6) or (front == 1 and top == 2):\n            return [\"R\", num]\n\n    if num == 5:\n        if (front == 1 and top == 3) or (front == 3 and top == 6) or (front == 6 and top == 4) or (front == 4 and top == 1):\n            return [\"L\", num]\n        elif (front == 3 and top == 1) or (front == 6 and top == 3) or (front == 4 and top == 6) or (front == 1 and top == 4):\n            return [\"R\", num]\n\n    if num == 6:\n        if (front == 2 and top == 4) or (front == 4 and top == 5) or (front == 5 and top == 3) or (front == 3 and top == 2):\n            return [\"L\", num]\n        elif (front == 4 and top == 2) or (front == 5 and top == 4) or (front == 3 and top == 5) or (front == 2 and top == 3):\n            return [\"R\", num]\n\n\ndef can_roll(dir, nowi, nowj, maps):\n    I = 0\n    J = 0\n    if dir == \"F\":\n        I += 1\n    if dir == \"B\":\n        I -= 1\n    if dir == \"R\":\n        J += 1\n    if dir == \"L\":\n        J -= 1\n    if maps[nowi][nowj][0] >= maps[nowi + I][nowj + J][0] + 1:\n        return True\n    return False\n\n\ndef roll(maps, nowi, nowj, top, front):\n    roll_num = get_num(top)\n    # print(roll_num, front, top)\n    dir1_list = get_dir(roll_num[0], front, top)\n    dir2_list = get_dir(roll_num[1], front, top)\n    # print(dir1_list, dir2_list)\n    dir1 = dir1_list[0]\n    dir2 = dir2_list[0]\n    # print(dir1, dir2)\n    if can_roll(dir1, nowi, nowj, maps):\n        # print(nowi, nowj, dir1, 7 - dir1_list[1])\n        I = 0\n        J = 0\n        if dir1 == \"F\":\n            I += 1\n            front = top\n        if dir1 == \"B\":\n            I -= 1\n            front = 7 - top\n        if dir1 == \"R\":\n            J += 1\n        if dir1 == \"L\":\n            J -= 1\n        maps = roll(maps, nowi + I, nowj + J, 7 - dir1_list[1], front)\n    elif can_roll(dir2, nowi, nowj, maps):\n        # print(nowi, nowj, dir2, 7 - dir2_list[1])\n        I = 0\n        J = 0\n        if dir2 == \"F\":\n            I += 1\n            front = top\n        if dir2 == \"B\":\n            I -= 1\n            front = 7 - top\n        if dir2 == \"R\":\n            J += 1\n        if dir2 == \"L\":\n            J -= 1\n        maps = roll(maps, nowi + I, nowj + J, 7 - dir2_list[1], front)\n    else:\n        maps[nowi][nowj][0] += 1\n        maps[nowi][nowj][1] = top\n    return maps\n\nwhile True:\n    n = int(input())\n    if not n:\n        break\n\n    maps = [[[0, 0] for _ in range(201)] for _ in range(201)]\n    nowi = 100\n    nowj = 100\n    for i in range(n):\n        t, f = map(int, input().split())\n        maps = roll(maps, nowi, nowj, t, f)\n    cnt = [0 for _ in range(6)]\n    for i in range(len(maps)):\n        for j in range(len(maps[i])):\n            if maps[i][j][1]:\n                cnt[maps[i][j][1] - 1] += 1\n    for i in range(len(cnt)):\n        cnt[i] = str(cnt[i])\n    # print(maps[100])\n    print(\" \".join(cnt))\n\n", "class RollDir:\n    def __init__(self, d, w):\n        self.d = d\n        self.w = w\n\n    def __str__(self):\n        return \"Roll dir: {}, weight: {}\".format(self.d, self.w)\n\n    @classmethod\n    def create(cls, d, w):\n        if w == 6 or w == 5 or w == 4:\n            return cls(d, w)\n        else:\n            return None\n\nclass Dice:\n    def __init__(self, t, f):\n        self.top = t\n        self.bot = 7 - t\n\n        if t == 1:\n            arr = [2, 3, 5, 4]\n        elif t == 6:\n            arr = [5, 3, 2, 4]\n        elif t == 2:\n            arr = [3, 1, 4, 6]\n        elif t == 5:\n            arr = [3, 6, 4, 1]\n        elif t == 3:\n            arr = [6, 5, 1, 2]\n        elif t == 4:\n            arr = [1, 5, 6, 2]\n\n        idx = arr.index(f)\n        self.front = arr[idx]\n        self.right = arr[(idx + 1) % 4]\n        self.back = arr[(idx + 2) % 4]\n        self.left = arr[(idx + 3) % 4]\n\n    def roll(self, direction):\n        if direction == 'N':\n            temp = self.top\n            self.top = self.front\n            self.front = self.bot\n            self.bot = self.back\n            self.back = temp\n        elif direction == 'E':\n            temp = self.top\n            self.top = self.left\n            self.left = self.bot\n            self.bot = self.right\n            self.right = temp\n        elif direction == 'W':\n            temp = self.top\n            self.top = self.right\n            self.right = self.bot\n            self.bot = self.left\n            self.left = temp\n        elif direction == 'S':\n            temp = self.top\n            self.top = self.back\n            self.back = self.bot\n            self.bot = self.front\n            self.front = temp\n\n    def getRollDir(self):\n        arr = []\n        roll = RollDir.create('S', self.front)\n        if roll != None:\n            arr.append(roll)\n        roll = RollDir.create('E', self.right)\n        if roll != None:\n            arr.append(roll)\n        roll = RollDir.create('N', self.back)\n        if roll != None:\n            arr.append(roll)\n        roll = RollDir.create('W', self.left)\n        if roll != None:\n            arr.append(roll)\n\n        return sorted(arr, key=lambda x: x.w ,reverse=True)\n        \n    def __str__(self):\n        return \"Top: {}   Front: {}   Left: {}   Right: {}\" \\\n            .format(self.top, self.front, self.left, self.right)\n\nclass Cell:\n    def __init__(self):\n        self.height = 0\n        self.val = None\n\nclass Grid:\n    def __init__(self):\n        self.cells = {}\n\n    def drop(self, dice, x, y):\n        if (x, y) not in self.cells:\n            self.cells[ (x, y) ] = Cell()\n        cell = self.cells[ (x, y) ]\n\n        diceRollDirs = dice.getRollDir()\n        gridRollDirs = self.getRollableDir(x, y)\n\n        didRoll = False\n        for roll in diceRollDirs:\n            if roll.d in gridRollDirs:\n                direction = roll.d\n                dice.roll(direction)\n                rollCoord = self.getRollCoord(x, y, direction)\n                self.drop(dice, rollCoord[0], rollCoord[1])\n                didRoll = True\n                break\n        \n        if not didRoll:\n            cell.height += 1\n            cell.val = dice.top\n\n    def getRollableDir(self, x, y):\n        if (x, y) not in self.cells:\n            self.cells[(x, y)] = Cell()\n        cell = self.cells[(x, y)]\n\n        arr = []\n        if cell.height == 0:\n            return []\n        if (x-1, y) not in self.cells or self.cells[(x-1, y)].height < cell.height:\n            arr.append('N')\n        if (x, y+1) not in self.cells or self.cells[(x, y+1)].height < cell.height:\n            arr.append('E')\n        if (x, y-1) not in self.cells or self.cells[(x, y-1)].height < cell.height:\n            arr.append('W')\n        if (x+1, y) not in self.cells or self.cells[(x+1, y)].height < cell.height:\n            arr.append('S')\n        return arr\n\n    def getRollCoord(self, x, y, d):\n        if d == 'N':\n            return (x-1, y)\n        elif d == 'E':\n            return (x, y+1)\n        elif d == 'W':\n            return (x, y-1)\n        elif d == 'S':\n            return (x+1, y)\n\n    def countVals(self):\n        count = [0, 0, 0, 0, 0, 0]\n        for coord in self.cells:\n            cell = self.cells[coord]\n            count[ cell.val - 1 ] += 1\n        return count\n\n\nif __name__ == '__main__':\n    while True:\n        N = int(input())\n        if N == 0:\n            break\n\n        grid = Grid()\n        for _ in range(N):\n            t, f = [ int(x) for x in list(filter(lambda x: x != '', \\\n                input().strip().split(' '))) ]\n            dice = Dice(t, f)\n            grid.drop(dice, 0, 0)\n\n        print(\" \".join(list(map(str, grid.countVals()))))\n", "MAXN = 50\nFIELD = [[[0]*MAXN for i in range(MAXN)] for j in range(MAXN)]\n\n\nclass Dice:\n    # . . U .  . . 1 .\n    # B L F R  4 2 3 5\n    # . . D .  . . 6\n    def __init__(self, t, f):\n        self.face = {}\n        self.face['F'] = f\n        self.face['U'] = t\n        self.face['B'] = 7 - f\n        self.face['D'] = 7 - t\n        r = 0\n        if [t, f] in [[4, 2], [2, 3], [3, 5], [5, 4]]:\n            r = 1\n        if [t, f] in [[4, 6], [6, 3], [3, 1], [1, 4]]:\n            r = 2\n        if [t, f] in [[1, 2], [2, 6], [6, 5], [5, 1]]:\n            r = 3\n        if [t, f] in [[2, 1], [6, 2], [5, 6], [1, 5]]:\n            r = 4\n        if [t, f] in [[1, 3], [3, 6], [6, 4], [4, 1]]:\n            r = 5\n        if [t, f] in [[2, 4], [3, 2], [5, 3], [4, 5]]:\n            r = 6\n\n        self.face['R'] = r\n        self.face['L'] = 7 - r\n\n    def find_face(self, f):\n        for i in 'FRUBLD':\n            if self.face[i] == f:\n                return i\n        return -1\n\n    def rotate(self, a, b, c, d):\n        t = self.face[d]\n        self.face[d] = self.face[c]\n        self.face[c] = self.face[b]\n        self.face[b] = self.face[a]\n        self.face[a] = t\n\n    def turn(self, dir):\n        if dir == 'R':\n            self.rotate('U', 'R', 'D', 'L')\n        if dir == 'B':\n            self.rotate('U', 'B', 'D', 'F')\n        if dir == 'L':\n            self.rotate('U', 'L', 'D', 'R')\n        if dir == 'F':\n            self.rotate('U', 'F', 'D', 'B')\n        if dir == 'U':\n            self.rotate('F', 'R', 'B', 'L')  # \u4e0a\u304b\u3089\u898b\u3066\u53cd\u6642\u8a08\u56de\u308a\n        if dir == 'D':\n            self.rotate('F', 'L', 'B', 'R')  # \u4e0b\u304b\u3089\u898b\u3066\u53cd\u6642\u8a08\u56de\u308a\n\n\ndef drop_dice(t, f):\n    global FIELD\n    dice = Dice(t, f)\n    x, y, h = MAXN//2, MAXN//2, 0\n    while FIELD[h][y][x] != 0:\n        h += 1\n    while h != 0:\n        is_not_turned = True\n        for i in [6, 5, 4]:\n            direction = dice.find_face(i)\n            if direction in 'UD':\n                continue\n            xj, yj = {'F': [x, y+1], 'L': [x-1, y],\n                      'B': [x, y-1], 'R': [x+1, y]}[direction]\n            for hj in range(0,h):\n                if FIELD[hj][yj][xj] == 0:\n                    x, y, h = xj, yj, hj\n                    dice.turn(direction)\n                    is_not_turned = False\n                    break\n            if is_not_turned == False:\n                break\n        if is_not_turned:\n            break\n    FIELD[h][y][x] = dice.face['U']\n    return\n\n\ndef count_top():\n    ans = [0]*6\n    looked = [[False]*MAXN for i in range(MAXN)]\n    for h in range(MAXN-1, -1, -1):\n        for x in range(MAXN):\n            for y in range(MAXN):\n                if looked[x][y] or FIELD[h][x][y] == 0:\n                    continue\n                ans[FIELD[h][x][y]-1] += 1\n                looked[x][y] = True\n    return ans\n\n\ndef main():\n    global FIELD\n    while True:\n        n = int(input())\n        if n == 0:\n            break\n        FIELD = [[[0]*MAXN for i in range(MAXN)] for j in range(MAXN)]\n        for i in range(n):\n            t, f = map(int, input().split())\n            drop_dice(t, f)\n        print(*count_top())\n\n\nif __name__ == '__main__':\n    main()\n\n", "class Dice:\n\n  def __init__(self, top=1, front=2, left=4, right=3, back=5, bottom=6):\n    self.d = {\"TOP\": top, \"FRONT\": front, \"LEFT\": left, \"RIGHT\": right, \"BACK\": back, \"BOTTOM\": bottom}\n\n  def roll_x(self):\n    self._roll(\"TOP\", \"FRONT\", \"BOTTOM\", \"BACK\")\n\n  def roll_y(self):\n    self._roll(\"FRONT\", \"LEFT\", \"BACK\", \"RIGHT\")\n\n  def roll_z(self):\n    self._roll(\"TOP\", \"LEFT\", \"BOTTOM\", \"RIGHT\")\n\n  def _roll(self, a, b, c, d):\n    self.d[a], self.d[b], self.d[c], self.d[d] = self.d[b], self.d[c], self.d[d], self.d[a]\n\n  def all_rolls(self):\n    import copy\n    ret = []\n    for i in range(6):\n      if i % 2:\n        self.roll_x()\n      else:\n        self.roll_y()\n      for _ in range(4):\n        self.roll_z()\n        ret.append(copy.deepcopy(self))\n    return ret\n\nimport copy\nfrom collections import defaultdict\nwhile True:\n  n = int(input())\n  if n==0:\n    break\n\n  board = [[0 for i in range(100)] for j in range(100)]\n  height = [[0 for i in range(100)] for j in range(100)]\n\n  for i in range(n):\n    t, f = list(map(int, input().split()))\n    dice = Dice()\n    for di in dice.all_rolls():\n      if di.d[\"TOP\"]==t and di.d[\"FRONT\"]==f:\n        break\n\n    x, y = 50, 50\n    while True:\n      dxy = []\n      for s in [\"FRONT\", \"LEFT\", \"BACK\", \"RIGHT\"]:\n        tt = di.d[s]\n        if tt>=4:\n          dxy.append((tt, s))\n      dxy.sort(reverse=True)\n\n      move = False\n      for _, s in dxy:\n        newdice = copy.deepcopy(di)\n        if s==\"FRONT\":\n          dx = 0\n          dy = 1\n          newdice.roll_x()\n          newdice.roll_x()\n          newdice.roll_x()\n        elif s==\"LEFT\":\n          dx = -1\n          dy = 0\n          newdice.roll_z()\n          newdice.roll_z()\n          newdice.roll_z()\n        elif s==\"BACK\":\n          dx = 0\n          dy = -1\n          newdice.roll_x()\n        elif s==\"RIGHT\":\n          dx = 1\n          dy = 0\n          newdice.roll_z()\n\n        if height[x][y]>height[x+dx][y+dy]:\n          x = x+dx\n          y = y+dy\n          di = newdice\n          move = True\n          break\n\n      if not move:\n        board[x][y] = di.d[\"TOP\"]\n        height[x][y] += 1\n        break\n\n  ans = defaultdict(int)\n  for e in board:\n    for ee in e:\n      ans[ee] += 1\n  print(*[ans[i] for i in range(1, 7)])\n", "# coding: UTF-8\nimport sys\n\nclass Dice:\n    #\u30b5\u30a4\u30b3\u30ed\u306e\u5168\u72b6\u614b(u,d,f,b,l,r\u306e\u9806)(u+d=f+b=l+r=7\u304c\u6210\u308a\u7acb\u3064)\n    state=[[1,6,2,5,4,3],[1,6,3,4,2,5],[1,6,4,3,5,2],[1,6,5,2,3,4],\n           [2,5,1,6,3,4],[2,5,3,4,6,1],[2,5,4,3,1,6],[2,5,6,1,4,3],\n           [3,4,1,6,5,2],[3,4,2,5,1,6],[3,4,5,2,6,1],[3,4,6,1,2,5],\n           [4,3,1,6,2,5],[4,3,2,5,6,1],[4,3,5,2,1,6],[4,3,6,1,5,2],\n           [5,2,1,6,4,3],[5,2,3,4,1,6],[5,2,4,3,6,1],[5,2,6,1,3,4],\n           [6,1,2,5,3,4],[6,1,3,4,5,2],[6,1,4,3,2,5],[6,1,5,2,4,3]]\n\n    #u,d,f,b,l,r\u3092\u305d\u308c\u305e\u308c0,1,2,3,4,5\u3068\u3057\u3066state1,state2\u306b\u6307\u5b9a\n    #value1,value2\u306f\u305d\u308c\u305e\u308cstate1,state2\u306b\u5bfe\u5fdc\u3059\u308b\u9762\u306e\u76ee\n    #now\u306f\u521d\u671f\u4f4d\u7f6e\u306e\u5ea7\u6a19\n    #\u9069\u5207\u3067\u306a\u3044\u5834\u5408\u306f\u30a8\u30e9\u30fc\u51fa\u529b\n    def __init__(self,state1,value1,state2,value2,now):\n        self.now=[now[0],now[1]]\n        for i in range(24):\n            if Dice.state[i][state1]==value1 and Dice.state[i][state2]==value2:\n                self.u,self.d,self.f,self.b,self.l,self.r=Dice.state[i]\n                break\n        else:\n            print('Error:Constructor\\'s Argument is missing.',file=sys.stderr)\n            exit()\n\n    #\u4e0a\u304b\u3089\u898b\u3066y\u8ef8\u306e+\u65b9\u5411\u306b\u56de\u8ee2(\u5f8c\u9762\u304c\u4e0b\u9762\u306b\uff01)\n    def RotateN(self):\n        self.d,self.f,self.u,self.b=self.b,self.d,self.f,self.u\n        self.now[1]+=1\n\n    #\u4e0a\u304b\u3089\u898b\u3066y\u8ef8\u306e-\u65b9\u5411\u306b\u56de\u8ee2(\u524d\u9762\u304c\u4e0b\u9762\u306b\uff01)\n    def RotateS(self):\n        self.d,self.f,self.u,self.b=self.f,self.u,self.b,self.d\n        self.now[1]-=1\n\n    #\u4e0a\u304b\u3089\u898b\u3066x\u8ef8\u306e+\u65b9\u5411\u306b\u56de\u8ee2(\u53f3\u9762\u304c\u4e0b\u9762\u306b\uff01)\n    def RotateE(self):\n        self.d,self.l,self.u,self.r=self.r,self.d,self.l,self.u\n        self.now[0]+=1\n\n    #\u4e0a\u304b\u3089\u898b\u3066x\u8ef8\u306e-\u65b9\u5411\u306b\u56de\u8ee2(\u5de6\u9762\u304c\u4e0b\u9762\u306b\uff01)\n    def RotateW(self):\n        self.d,self.l,self.u,self.r=self.l,self.u,self.r,self.d\n        self.now[0]-=1\n\n    #\u524d\u304b\u3089\u898b\u3066\u5de6\u56de\u8ee2(\u53cd\u6642\u8a08\u56de\u308a)\n    def RotateL(self):\n        self.f,self.l,self.b,self.r=self.r,self.f,self.l,self.b\n\n    #\u524d\u304b\u3089\u898b\u3066\u53f3\u56de\u8ee2(\u6642\u8a08\u56de\u308a)\n    def RotateR(self):\n        self.f,self.l,self.b,self.r=self.l,self.b,self.r,self.f\n\n#\u5ea7\u6a19\u3068\u30b5\u30a4\u30b3\u30ed\u306e\u60c5\u5831\u3092\u4e0e\u3048\u308b\ndef move(i):\n    global n,rec,sai\n    #\u79fb\u52d5\u5148\u3068\u305d\u3053\u306b\u79fb\u52d5\u3067\u304d\u308b\u306e\u304b\u306e\u5224\u65ad\n    #\u8907\u6570\u79fb\u52d5\u3067\u304d\u308b\u53ef\u80fd\u6027(\u305d\u306e\u4e2d\u3067\u5927\u304d\u3044\u3082\u306e)\n    #\u5927\u304d\u3044\u9806\u306b\u4e26\u3079\u308b\n    now=[sai[i].now[0],sai[i].now[1]]\n    for j in range(6,3,-1):\n        if j==sai[i].f:\n            sai[i].RotateS()\n            check=0\n        elif j==sai[i].b:\n            sai[i].RotateN()\n            check=1\n        elif j==sai[i].l:\n            sai[i].RotateW()\n            check=2\n        elif j==sai[i].r:\n            sai[i].RotateE()\n            check=3\n        else:\n            continue\n        if rec[now[0]][now[1]][1]>rec[sai[i].now[0]][sai[i].now[1]][1]:\n            move(i)\n            return\n        #\u3053\u3053\u3067\u623b\u3057\u305f\u3044\n        func=[sai[i].RotateN,sai[i].RotateS,sai[i].RotateE,sai[i].RotateW]\n        func[check]()\n    else:\n        rec[sai[i].now[0]][sai[i].now[1]][0]=sai[i].u\n        rec[sai[i].now[0]][sai[i].now[1]][1]+=1\n\nmaxr=205\nwhile True:\n    n=int(input())\n    if n==0:\n        break\n    #\u30b5\u30a4\u30b3\u30ed\n    sai=[]\n    for i in range(n):\n        x,y=map(int,input().split())\n        sai.append(Dice(0,x,2,y,[maxr//2,maxr//2]))\n    #\u5ea7\u6a19(\u521d\u3081\u306f(100,100)\u3001\u5411\u304d\u306f(1,0))\n    #(\u5024,\u9ad8\u3055)\n    rec=[[[0,0] for j in range(maxr)] for i in range(maxr)]\n    rec[maxr//2][maxr//2]=[sai[0].u,1]\n    for i in range(1,n):\n        move(i)\n    ans=[0]*6\n    for i in range(maxr):\n        for j in range(maxr):\n            if rec[i][j][0]!=0:\n                ans[rec[i][j][0]-1]+=1\n    print(\" \".join(map(str,ans)))\n", "#! cat input | python3 main.py\ndef debug():\n    for X in field[size//2:] + field[:size//2]:\n        print(X[size//2:], X[:size//2])\n\ndice_data = [[],\n        [4, 2, 3, 5],\n        [4, 6, 3, 1],\n        [6, 5, 1, 2],\n        [1, 5, 6, 2],\n        [4, 1, 3, 6],\n        [4, 5, 3, 2],\n        ]\ndef dice(t, f):\n    i = dice_data[t].index(f)\n    return [dice_data[t][x%4] for x in range(i, i + 4)]\n\nsize = 6\nmove = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n\ndef drop(t, f, nowl, nowr):\n    target = list(map(lambda x: x > 3, dice(t, f)))\n    now = [nowl, nowr]\n    \n    now_field = field[now[0]][now[1]]\n    for i, tg in enumerate(target):\n        if tg:\n            nb_field = field[now[0] + move[i][0]][now[1] + move[i][1]]\n            if nb_field[1] >= now_field[1]:\n                target[i] = False\n    for i, v in sorted(enumerate(dice(t, f)), key=lambda x: x[1], reverse=True):\n        if target[i]:\n            if i == 0:\n                f = t\n            elif i == 2:\n                f = 7 - t\n            t = 7 - v\n            drop(t, f, now[0] + move[i][0], now[1] + move[i][1])\n            break\n    else:\n        change = field[now[0]][now[1]]\n        change[0] = t\n        change[1] += 1\n\nwhile True:\n    n = int(input())\n    if not n: break\n    field = [[[0, 0] for i in range(size)] for j in range(size)]\n\n    tfs = [list(map(int, input().split())) for x in range(n)]\n    for t, f in tfs:\n        drop(t, f, 0, 0)\n    cnt = [0 for x in range(7)]\n    for row in field:\n        for cell in row:\n            cnt[cell[0]] += 1\n    print(*cnt[1:])\n", "D = [0 for _ in range(6)]\nD[0] = [2, 3, 5, 4]\nD[1] = [1, 4, 6, 3]\nD[2] = [5, 1, 2, 6]\nD[3] = [1, 5, 6, 2]\nD[4] = [3, 6, 4, 1]\nD[5] = [3, 2, 4, 5]\nfor i in range(6):\n    for j in range(4):\n        D[i][j] -= 1\n\nwhile True:\n    n = int(input())\n    if n == 0:\n        break\n    H = [[0 for _ in range(41)] for _ in range(41)]\n    num = [[6 for _ in range(41)] for _ in range(41)]\n\n    def solve(i, j, t, f):\n        global H, num\n        if H[i][j] == 0:\n            H[i][j] = 1\n            num[i][j] = t\n            return\n        tmp = D[t]\n        idx = 0\n        for di, x in enumerate(tmp):\n            if x == f:\n                idx = di\n        nxt = []\n        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:\n            nxt.append((tmp[idx], di, dj))\n            idx = (idx+1) % 4\n        h = H[i][j]\n        for v in range(5, 2, -1):\n            if v == t or v == 5-t:\n                continue\n            for z, (x, di, dj) in enumerate(nxt):\n                if x != v:\n                    continue\n                if H[i+di][j+dj] >= h:\n                    continue\n                nt = 5-v\n                if z == 0:\n                    nf = t\n                elif z == 1:\n                    nf = f\n                elif z == 2:\n                    nf = 5-t\n                else:\n                    nf = f\n                solve(i+di, j+dj, nt, nf)\n                return\n        H[i][j] += 1\n        num[i][j] = t\n        return\n\n    for _ in range(n):\n        t, f = map(lambda x: int(x)-1, input().split())\n        solve(20, 20, t, f)\n    res = [0 for _ in range(7)]\n    for X in num:\n        for x in X:\n            res[x] += 1\n    print(*res[:-1])\n\n", "from collections import defaultdict\n\n\ndef roll(die, i):\n    a,b,c,d = ((1,2,4,3), (0,4,5,1), (0,3,5,2), (0,2,5,3), (0,1,5,4))[i]\n    die[a], die[b], die[c], die[d] = die[b], die[c], die[d], die[a]\n\n\nwhile True:\n    n = int(input())\n    if n == 0:\n        break\n    count = [0] * 7\n    m = defaultdict(int)\n    for _ in range(n):\n        top, front = map(int, input().split())\n        die = [1, 2, 3, 4, 5, 6]\n        while die[0] != top:\n            roll(die, 1)\n            die[0] != top and roll(die, 2)\n        while die[1] != front:\n            roll(die, 0)\n        x, y, z = 0, 0, 0\n        while m[x, y, z]:\n            while m[x, y, z]:\n                z += 1\n            number = 3\n            for f, nx, ny in (1, x, y+1), (2, x+1, y), (3, x-1, y), (4, x, y-1):\n                if die[f] > number and m[nx, ny, z] == m[nx, ny, z-1] == 0:\n                    number, r, x, y = die[f], f, nx, ny\n            if number == 3:\n                break\n            roll(die, r)\n            z = 0\n        m[x, y, z] = die[0]\n        count[m[x, y, z-1]] -= 1\n        count[m[x, y, z]] += 1\n    print(*count[1:])\n\n"]

source: aizu

question:
Biased Dice

Professor Random, known for his research on randomized algorithms, is now conducting an experiment on biased dice.  His experiment consists of dropping a number of dice onto a plane, one after another from a fixed position above the plane.  The dice fall onto the plane or dice already there, without rotating, and may roll and fall according to their property.  Then he observes and records the status of the stack formed on the plane, specifically, how many times each number appears on the faces visible from above. All the dice have the same size and their face numbering is identical, which we show in Figure C-1.

![image](1.png)

Figure C-1: Numbering of a die

The dice have very special properties, as in the following.

(1) Ordinary dice can roll in four directions, but the dice used in this experiment never roll in the directions of faces 1, 2 and 3; they can only roll in the directions of faces 4, 5 and 6.  In the situation shown in Figure C-2, our die can only roll to one of two directions.

![image](2.png)

Figure C-2: An ordinary die and a biased die

(2) The die can only roll when it will fall down after rolling, as shown in Figure C-3.  When multiple possibilities exist, the die rolls towards the face with the largest number among those directions it can roll to.

![image](3.png)

Figure C-3: A die can roll only when it can fall

(3) When a die rolls, it rolls exactly 90 degrees, and then falls straight down until its bottom face touches another die or the plane, as in the case [B] or [C] of Figure C-4.

(4) After rolling and falling, the die repeatedly does so according to the rules (1) to (3) above.

![image](4.png)

Figure C-4: Example stacking of biased dice

For example, when we drop four dice all in the same orientation, 6 at the top and 4 at the front, then a stack will be formed as shown in Figure C-4.

![image](5.png)

Figure C-5: Example records

After forming the stack, we count the numbers of faces with 1 through 6 visible from above and record them.  For example, in the left case of Figure C-5, the record will be "0 2 1 0 0 0", and in the right case, "0 1 1 0 0 1".

Input

The input consists of several datasets each in the following format.

n
t_{1}  f_{1}
t_{2}  f_{2}
...
t_{n}  f_{n}

Here, n (1 ≤ n ≤ 100) is an integer and is the number of the dice to be dropped.  t_{i} and f_{i} (1 ≤ t_{i}, f_{i} ≤ 6) are two integers separated by a space and represent the numbers on the top and the front faces of the i-th die, when it is released, respectively.

The end of the input is indicated by a line containing a single zero.

Output

For each dataset, output six integers separated by a space. The integers represent the numbers of faces with 1 through 6 correspondingly, visible from above. There may not be any other characters in the output.

Sample Input

4
6 4
6 4
6 4
6 4
2
5 3
5 3
8
4 2
4 2
4 2
4 2
4 2
4 2
4 2
4 2
6
4 6
1 5
2 3
5 3
2 4
4 2
0

Output for the Sample Input

0 1 1 0 0 1
1 0 0 0 1 0
1 2 2 1 0 0
2 3 0 0 0 0

image_tags:
3D Geometry
3D Geometry
3D Geometry
3D Geometry
3D Geometry

data_split: test


Checkered Pattern

source: Ritsumeikan University Programming Contest 2015, University of Aizu Competitive Programming Camp 2015

raw_problem:
D : 市松模様 / Checkered Pattern

問題文

縦横の長さが <var>h, w</var> の長方形があり， 内部には一辺の長さが <var>1</var> の正方形のマスが敷き詰められている． 最も左上のマスを <var>(0,0)</var> とし， <var>(0,0)</var> の <var>i</var> 個下で <var>j</var> 個右のマスを <var>(i,j)</var> のように表すことにすると， <var>(i,j)</var> は <var>i+j</var> が偶数なら赤色に，奇数なら青色に塗られている．

今，<var>(0,0)</var> の左上の頂点と <var>(h − 1,w − 1)</var> の右下の頂点を線分で結んだ． この線分が通る赤色の部分の長さを <var>a</var>, 青色の部分の長さを <var>b</var> とおいたとき， 比 <var>a : b</var> は整数比となる．<var>a : b</var> を最も簡単にして(互いに素な整数で)表せ．

入力

<var>T</var>
<var>h_1 \ w_1</var>
<var>…</var>
<var>h_T \ w_T</var>

<var>1</var> つのファイルに <var>T</var> 個の入力が含まれる． <var>1</var> 行目に <var>T</var>， <var>1+i</var> 行目に <var>T</var> 番目の入力における縦横の長さ <var>h_i</var>, <var>w_i</var> が入力される．

制約

整数である

<var>1 ≤ T ≤ 1000</var>

<var>1 ≤ h_i, w_i ≤ 109</var>

出力

各ケースに対する答えを <var>1</var> でスペース区切りで出力せよ． 全体で <var>T</var> 行にわたる．

サンプル

サンプル入力1

3
2 3
3 3
4 3

サンプル出力1

1 1
1 0
1 1

solutions: ["def gcd(a,b):\n    if a == 0:\n        return b\n    else:\n        return gcd(b%a,a)\nt = int(input())\nwhile t:\n    t -= 1\n    a,b = map(int, input().split())\n    c = gcd(a,b)\n    a = a//c\n    b = b//c\n    if a == b:\n        ans1 = 1\n        ans2 = 0\n    elif a % 2 == 0 or b % 2 == 0:\n        ans1 = 1\n        ans2 = 1\n    else:\n        ans1 = a*b//2+1\n        ans2 = a*b//2\n    print(ans1,ans2)\n"]

source: aizu

question:
D: Checkered Pattern
Problem Statement
There is a rectangle of vertical and horizontal lengths $h, w$ that is tiled with square cells of side length $1$. The top-left cell of the rectangle is designated as $(0,0)$, and the cell $i$ steps down and $j$ steps to the right of $(0,0)$ is represented as $(i,j)$. If $i+j$ is even, then the cell $(i,j)$ is colored red, and if odd, it is colored blue.
Now, a line segment is drawn connecting the top-left vertex of $(0,0)$ and the bottom-right vertex of $(h − 1,w − 1)$. Define the length of the segment passing through the red part as $a$ and the length passing through the blue part as $b$. The ratio $a : b$ will be an integer ratio. Express $a : b$ in its simplest form (as coprime integers).
Input

$T$

$h_1 \ w_1$

$…$

$h_T \ w_T$

A single file contains $T$ inputs. Line $1$ contains $T$, and the vertical and horizontal lengths $h_i$, $w_i$ for the $T$th input are given on line $1+i$.
Constraints

- Are integers
- $1 ≤ T ≤ 1000$
- $1 ≤ h_i, w_i ≤ 10^{9}$

Output
Output the answer for each case, separated by a space on one line. The output will span $T$ lines in total.
Sample
Sample Input 1

3
2 3
3 3
4 3

Sample Output 1

1 1
1 0
1 1

![image](1.png)

data_split: test


C. Max Mex

problem_index: C

time_limit: 3 seconds

memory_limit: 256 megabytes

note:
Number written in brackets is a permutation value of a node.
![image](images/cf_1083_C/1.png)
![image](images/cf_1083_C/2.png)
![image](images/cf_1083_C/3.png)
![image](images/cf_1083_C/4.png)
![image](images/cf_1083_C/5.png)
![image](images/cf_1083_C/6.png)
![image](images/cf_1083_C/7.png)

source: codeforces

raw_problem:
C. Max Mex

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Once Grisha found a tree (connected graph without cycles) with a root in node $$$1$$$.

But this tree was not just a tree. A permutation $$$p$$$ of integers from $$$0$$$ to $$$n - 1$$$ is written in nodes, a number $$$p_i$$$ is written in node $$$i$$$.

As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.

Let's define a function $$$MEX(S)$$$, where $$$S$$$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.

Let $$$l$$$ be a simple path in this tree. So let's define indices of nodes which lie on $$$l$$$ as $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$.

Define $$$V(l)$$$ as a set {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}.

Then queries are:

 For two nodes $$$i$$$ and $$$j$$$, swap $$$p_i$$$ and $$$p_j$$$.

 Find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of nodes of a tree.

The second line contains $$$n$$$ integers — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — the permutation $$$p$$$, it's guaranteed that all numbers are different .

The third line contains $$$n - 1$$$ integers — $$$d_2$$$, $$$d_3$$$, $$$\ldots$$$, $$$d_n$$$ ($$$1 \leq d_i < i$$$), where $$$d_i$$$ is a direct ancestor of node $$$i$$$ in a tree.

The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain the description of queries:

At the beginning of each of next $$$q$$$ lines, there is a single integer $$$t$$$ ($$$1$$$ or $$$2$$$) — the type of a query:

 If $$$t = 1$$$, the line also contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$) — the indices of nodes, where values of the permutation should be swapped.

 If $$$t = 2$$$, you need to find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.

Output

For each type 2 query print a single integer — the answer for this query.

Examples

Input

6
2 5 0 3 1 4
1 1 3 3 3
3
2
1 6 3
2

Output

3
2

Input

6
5 2 1 4 3 0
1 1 1 3 3
9
2
1 5 3
2
1 6 1
2
1 4 2
2
1 1 6
2

Output

3
2
4
4
2

Note

Number written in brackets is a permutation value of a node.
   In the first example, for the first query, optimal path is a path from node $$$1$$$ to node $$$5$$$. For it, set of values is $$$\{0, 1, 2\}$$$ and $$$MEX$$$ is $$$3$$$.    For the third query, optimal path is a path from node $$$5$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 4\}$$$ and $$$MEX$$$ is $$$2$$$.    In the second example, for the first query, optimal path is a path from node $$$2$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 2, 5\}$$$ and $$$MEX$$$ is $$$3$$$.    For the third query, optimal path is a path from node $$$5$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 3\}$$$ and $$$MEX$$$ is $$$2$$$.    For the fifth query, optimal path is a path from node $$$5$$$ to node $$$2$$$. For it, set of values is $$$\{0, 1, 2, 3\}$$$ and $$$MEX$$$ is $$$4$$$.    For the seventh query, optimal path is a path from node $$$5$$$ to node $$$4$$$. For it, set of values is $$$\{0, 1, 2, 3\}$$$ and $$$MEX$$$ is $$$4$$$.    For the ninth query, optimal path is a path from node $$$6$$$ to node $$$5$$$. For it, set of values is $$$\{0, 1, 3\}$$$ and $$$MEX$$$ is $$$2$$$.

question:
Once Grisha found a tree (connected graph without cycles) with a root in node $$$1$$$.
But this tree was not just a tree. A permutation $$$p$$$ of integers from $$$0$$$ to $$$n - 1$$$ is written in nodes, a number $$$p_i$$$ is written in node $$$i$$$.
As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.
Let's define a function $$$MEX(S)$$$, where $$$S$$$ is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.
Let $$$l$$$ be a simple path in this tree. So let's define indices of nodes which lie on $$$l$$$ as $$$u_1$$$, $$$u_2$$$, $$$\ldots$$$, $$$u_k$$$.
Define $$$V(l)$$$ as a set {$$$p_{u_1}$$$, $$$p_{u_2}$$$, $$$\ldots$$$ , $$$p_{u_k}$$$}.
Then queries are:
 -  For two nodes $$$i$$$ and $$$j$$$, swap $$$p_i$$$ and $$$p_j$$$. -  Find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.
Input
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of nodes of a tree.
The second line contains $$$n$$$ integers — $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ ($$$0\leq p_i < n$$$) — the permutation $$$p$$$, it's guaranteed that all numbers are different .
The third line contains $$$n - 1$$$ integers — $$$d_2$$$, $$$d_3$$$, $$$\ldots$$$, $$$d_n$$$ ($$$1 \leq d_i < i$$$), where $$$d_i$$$ is a direct ancestor of node $$$i$$$ in a tree.
The fourth line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of queries.
The following $$$q$$$ lines contain the description of queries:
At the beginning of each of next $$$q$$$ lines, there is a single integer $$$t$$$ ($$$1$$$ or $$$2$$$) — the type of a query:
 -  If $$$t = 1$$$, the line also contains two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$) — the indices of nodes, where values of the permutation should be swapped. -  If $$$t = 2$$$, you need to find the maximum value of $$$MEX(V(l))$$$ in all possible $$$l$$$.
Output
For each type 2 query print a single integer — the answer for this query.

Examples
Input
6
2 5 0 3 1 4
1 1 3 3 3
3
2
1 6 3
2

Output
3
2

Input
6
5 2 1 4 3 0
1 1 1 3 3
9
2
1 5 3
2
1 6 1
2
1 4 2
2
1 1 6
2

Output
3
2
4
4
2

Note
Number written in brackets is a permutation value of a node.
 ![image](1.png)  In the first example, for the first query, optimal path is a path from node $$$1$$$ to node $$$5$$$. For it, set of values is $$$\{0, 1, 2\}$$$ and $$$MEX$$$ is $$$3$$$.  ![image](2.png)  For the third query, optimal path is a path from node $$$5$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 4\}$$$ and $$$MEX$$$ is $$$2$$$.  ![image](3.png)  In the second example, for the first query, optimal path is a path from node $$$2$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 2, 5\}$$$ and $$$MEX$$$ is $$$3$$$.  ![image](4.png)  For the third query, optimal path is a path from node $$$5$$$ to node $$$6$$$. For it, set of values is $$$\{0, 1, 3\}$$$ and $$$MEX$$$ is $$$2$$$.  ![image](5.png)  For the fifth query, optimal path is a path from node $$$5$$$ to node $$$2$$$. For it, set of values is $$$\{0, 1, 2, 3\}$$$ and $$$MEX$$$ is $$$4$$$.  ![image](6.png)  For the seventh query, optimal path is a path from node $$$5$$$ to node $$$4$$$. For it, set of values is $$$\{0, 1, 2, 3\}$$$ and $$$MEX$$$ is $$$4$$$.  ![image](7.png)  For the ninth query, optimal path is a path from node $$$6$$$ to node $$$5$$$. For it, set of values is $$$\{0, 1, 3\}$$$ and $$$MEX$$$ is $$$2$$$.

skill_types: ['Data structures']

image_tags: Tree Tree Tree Tree Tree Tree Tree

data_split: test


D. The Child and Sequence

problem_index: D

time_limit: 4 seconds

memory_limit: 256 megabytes

input_spec:
The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.
Each of the next m lines begins with a number type ![image](images/cf_438_D/2.png).
If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1.  If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2.  If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3.

question:
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.
Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:
 -  Print operation l, r. Picks should write down the value of ![image](1.png). -  Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r). -  Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x). Can you help Picks to perform the whole sequence of operations?

Input
The first line of input contains two integer: n, m (1 ≤ n, m ≤ 10^{5}). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^{9}) — initial value of array elements.
Each of the next m lines begins with a number type ![image](2.png).
 -  If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1. -  If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 10^{9}), which correspond the operation 2. -  If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 10^{9}), which correspond the operation 3.
Output
For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples
Input
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

Output
8
5

Input
10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

Output
49
15
23
1
9

Note
Consider the first testcase:
 -  At first, a = {1, 2, 3, 4, 5}. -  After operation 1, a = {1, 2, 3, 0, 1}. -  After operation 2, a = {1, 2, 5, 0, 1}. -  At operation 3, 2 + 5 + 0 + 1 = 8. -  After operation 4, a = {1, 2, 2, 0, 1}. -  At operation 5, 1 + 2 + 2 = 5.

difficulty: HARD

source: codeforces

raw_problem:
D. The Child and Sequence

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array a[1], a[2], ..., a[n]. Then he should perform a sequence of m operations. An operation can be one of the following:

 Print operation l, r. Picks should write down the value of .

 Modulo operation l, r, x. Picks should perform assignment a[i] = a[i] mod x for each i (l ≤ i ≤ r).

 Set operation k, x. Picks should set the value of a[k] to x (in other words perform an assignment a[k] = x).

Can you help Picks to perform the whole sequence of operations?

Input

The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105). The second line contains n integers, separated by space: a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — initial value of array elements.

Each of the next m lines begins with a number type .

 If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n), which correspond the operation 1.

 If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109), which correspond the operation 2.

 If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109), which correspond the operation 3.

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

Input

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

Output

8
5

Input

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

Output

49
15
23
1
9

Note

Consider the first testcase:

 At first, a = {1, 2, 3, 4, 5}.

 After operation 1, a = {1, 2, 3, 0, 1}.

 After operation 2, a = {1, 2, 5, 0, 1}.

 At operation 3, 2 + 5 + 0 + 1 = 8.

 After operation 4, a = {1, 2, 2, 0, 1}.

 At operation 5, 1 + 2 + 2 = 5.

skill_types: ['Data structures']

image_tags: Math Math

data_split: test


solutions: ["def sortedInsert(head, x):\n\tn = Node(x)\n\tif head is None:\n\t\thead = n\n\telif head.data >= n.data:\n\t\tn.next = head\n\t\tn.next.prev = n\n\t\thead = n\n\telse:\n\t\tcurrent = head\n\t\twhile current.next is not None and current.next.data < n.data:\n\t\t\tcurrent = current.next\n\t\tn.next = current.next\n\t\tif current.next is not None:\n\t\t\tn.next.prev = n\n\t\tcurrent.next = n\n\t\tn.prev = current\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tcur = head\n\tif head == None:\n\t\treturn temp\n\telif x < head.data:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\twhile cur.next != None and cur.next.data < x:\n\t\tcur = cur.next\n\tif cur.next == None:\n\t\ttemp.next = cur.next\n\t\tcur.next = temp\n\t\ttemp.prev = cur\n\telse:\n\t\ttemp.next = cur.next\n\t\tcur.next.prev = temp\n\t\tcur.next = temp\n\t\ttemp.prev = cur\n\treturn head\n", "def sortedInsert(head, x):\n\th = head\n\tnode = Node(x)\n\tif not head:\n\t\treturn node\n\telif head.data >= x:\n\t\tnode.next = head\n\t\tnode.next.prev = node\n\t\treturn node\n\tcurr = head\n\twhile curr.next and curr.next.data < x:\n\t\tcurr = curr.next\n\tnode.next = curr.next\n\tif curr.next:\n\t\tnode.next.prev = node\n\tcurr.next = node\n\tnode.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tcurr = head\n\twhile curr.next and curr.next.data < x:\n\t\tcurr = curr.next\n\tif curr == head and x < curr.data:\n\t\tn_node = Node(x)\n\t\tn_node.next = head\n\t\thead.prev = n_node\n\t\thead = n_node\n\telse:\n\t\tn_node = Node(x)\n\t\tn_node.prev = curr\n\t\tn_node.next = curr.next\n\t\tcurr.next = n_node\n\t\tif n_node.next != None:\n\t\t\tn_node.next.prev = n_node\n\treturn head\n", "def sortedInsert(head, x):\n\tnew = Node(x)\n\tif head is None:\n\t\treturn new\n\tif x < head.data:\n\t\tnew.next = head\n\t\thead.prev = new\n\t\treturn new\n\tcurr = head\n\twhile curr.next is not None:\n\t\tnxt = curr.next\n\t\tif x >= curr.data and x < nxt.data:\n\t\t\tcurr.next = new\n\t\t\tnew.prev = curr\n\t\t\tnew.next = nxt\n\t\t\tnxt.prev = new\n\t\t\treturn head\n\t\tcurr = curr.next\n\tcurr.next = new\n\tnew.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\ta = head\n\tp = []\n\twhile a is not None:\n\t\tp.append(a.data)\n\t\ta = a.next\n\tp.append(x)\n\tq = sorted(p)\n\thead1 = None\n\tnewnode = None\n\tfor i in q:\n\t\tm = Node(i)\n\t\tif head1 is None:\n\t\t\thead1 = m\n\t\t\tnewnode = head1\n\t\telse:\n\t\t\tnewnode.next = m\n\t\t\tm.prev = newnode\n\t\t\tnewnode = newnode.next\n\treturn head1\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tif head == None:\n\t\treturn None\n\tif temp.data < head.data:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\tcurr = head\n\tnode = Node(x)\n\twhile curr.next and curr.next.data < x:\n\t\tcurr = curr.next\n\tnode.next = curr.next\n\tif curr.next:\n\t\tnode.next.prev = node\n\tcurr.next = node\n\tnode.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\ttemp = head\n\tif temp.next is None:\n\t\tif temp.data > x:\n\t\t\tnew_node.next = temp\n\t\t\ttemp.prev = new_node\n\t\t\thead = new_node\n\t\telse:\n\t\t\ttemp.next = new_node\n\t\t\tnew_node.prev = temp\n\telif temp.data > x:\n\t\tnew_node.next = temp\n\t\ttemp.prev = new_node\n\t\thead = new_node\n\telse:\n\t\twhile temp.next != None:\n\t\t\tif temp.data > x:\n\t\t\t\tbreak\n\t\t\ttemp = temp.next\n\t\tif temp.next != None:\n\t\t\tnew_node.prev = temp.prev\n\t\t\tnew_node.next = temp\n\t\t\ttemp.prev.next = new_node\n\t\t\ttemp.prev = new_node\n\t\telif temp.data <= x:\n\t\t\ttemp.next = new_node\n\t\t\tnew_node.prev = temp\n\t\telse:\n\t\t\tnew_node.prev = temp.prev\n\t\t\tnew_node.next = temp\n\t\t\ttemp.prev.next = new_node\n\t\t\ttemp.prev = new_node\n\treturn head\n", "def sortedInsert(head, x):\n\tn = head\n\tN = Node(x)\n\tif n.data >= x:\n\t\tN.next = head\n\t\thead.prev = N\n\t\thead = N\n\telse:\n\t\twhile n.next != None:\n\t\t\tif n.data >= x:\n\t\t\t\tn.prev.next = N\n\t\t\t\tN.prev = n.Prev\n\t\t\t\tN.next = n\n\t\t\t\tn.prev = N\n\t\t\t\tbreak\n\t\t\tn = n.next\n\t\t\tif n.data >= x:\n\t\t\t\tn.prev.next = N\n\t\t\t\tN.prev = n.prev\n\t\t\t\tN.next = n\n\t\t\t\tn.prev = N\n\t\t\t\tbreak\n\t\telse:\n\t\t\tN.prev = n\n\t\t\tn.next = N\n\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\tif head.data >= x:\n\t\tnew_node.next = head\n\t\thead.prev = new_node\n\t\thead = new_node\n\telse:\n\t\tn = head\n\t\twhile n.next is not None:\n\t\t\tif n.next.data >= x:\n\t\t\t\tbreak\n\t\t\tn = n.next\n\t\tif n.next is None:\n\t\t\tn.next = new_node\n\t\t\tnew_node.prev = n\n\t\telse:\n\t\t\tnew_node.next = n.next\n\t\t\tn.next.prev = new_node\n\t\t\tnew_node.prev = n\n\t\t\tn.next = new_node\n\treturn head\n", "def sortedInsert(head, x):\n\tcurr = head\n\twhile curr and curr.next and (curr.data < x):\n\t\tcurr = curr.next\n\tif curr.data >= x:\n\t\tnew_node = Node(curr.data)\n\t\tcurr.data = x\n\t\tnew_node.next = curr.next\n\t\tif new_node.next:\n\t\t\tnew_node.next.prev = new_node\n\telse:\n\t\tnew_node = Node(x)\n\tnew_node.prev = curr\n\tcurr.next = new_node\n\treturn head\n", "def sortedInsert(head, x):\n\tn = Node(x)\n\tif head == None:\n\t\treturn n\n\tcurr = head\n\tif curr.data > x:\n\t\tn.next = curr\n\t\tcurr.prev = n\n\t\treturn n\n\twhile curr.next != None:\n\t\tif curr.next.data > x:\n\t\t\tbreak\n\t\tcurr = curr.next\n\tn.next = curr.next\n\tif curr.next != None:\n\t\tcurr.next.prev = n\n\tcurr.next = n\n\tn.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tnew = Node(x)\n\tif head == None:\n\t\treturn new\n\telif head.data >= new.data:\n\t\tnew.next = head\n\t\tnew.next.prev = new\n\t\thead = new\n\telse:\n\t\tcurr = head\n\t\twhile curr.next != None and curr.next.data < new.data:\n\t\t\tcurr = curr.next\n\t\tnew.next = curr.next\n\t\tif curr.next != None:\n\t\t\tcurr.next.prev = new\n\t\tcurr.next = new\n\t\tnew.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tif head is None:\n\t\treturn temp\n\tcurr = head\n\twhile curr and curr.next:\n\t\tif curr.data <= x and curr.next.data > x:\n\t\t\ttemp.next = curr.next\n\t\t\ttemp.prev = curr\n\t\t\tcurr.next.prev = temp\n\t\t\tcurr.next = temp\n\t\t\treturn head\n\t\telif x <= curr.data:\n\t\t\ttemp.next = curr\n\t\t\tcurr.prev = temp\n\t\t\treturn temp\n\t\tcurr = curr.next\n\tcurr.next = temp\n\ttemp.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\ts = Node(x)\n\tif x <= head.data:\n\t\ts.next = head\n\t\thead.prev = s\n\t\thead = s\n\t\treturn head\n\titr = head\n\tprev = None\n\twhile itr:\n\t\tprev = itr\n\t\titr = itr.next\n\tif prev.data < x:\n\t\tprev.next = s\n\t\ts.prev = prev\n\t\treturn head\n\titr = head\n\tprev = None\n\twhile itr.data <= x:\n\t\tprev = itr\n\t\titr = itr.next\n\tprev.next = s\n\titr.prev = s\n\ts.prev = prev\n\ts.next = itr\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tcurr = head\n\tc = 1\n\twhile curr.next is not None and curr.data < temp.data:\n\t\tcurr = curr.next\n\t\tc += 1\n\tif c == 1:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\tif curr.next is None:\n\t\tif curr.data < temp.data:\n\t\t\tcurr.next = temp\n\t\t\ttemp.prev = curr\n\t\t\treturn head\n\ttemp.next = curr\n\ttemp.prev = curr.prev\n\tcurr.prev.next = temp\n\tcurr.prev = temp\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tcurr = head\n\tprev = head\n\tif head.data >= x:\n\t\thead.prev = temp\n\t\ttemp.next = head\n\t\thead = temp\n\t\treturn head\n\twhile curr.next:\n\t\tif curr.data < x <= curr.next.data:\n\t\t\ttemp.prev = curr\n\t\t\ttemp.next = curr.next\n\t\t\tcurr.next.prev = temp\n\t\t\tcurr.next = temp\n\t\t\treturn head\n\t\telse:\n\t\t\tprev = curr\n\t\t\tcurr = curr.next\n\ttemp.prev = curr\n\tcurr.next = temp\n\treturn head\n", "class Node:\n\n\tdef __init__(self, data):\n\t\tself.data = data\n\t\tself.prev = None\n\t\tself.next = None\n\ndef sortedInsert(head, x):\n\tnew_node = Node(x)\n\tif head is None:\n\t\treturn new_node\n\tif x < head.data:\n\t\tnew_node.next = head\n\t\thead.prev = new_node\n\t\treturn new_node\n\tcurrent = head\n\twhile current.next is not None and current.next.data < x:\n\t\tcurrent = current.next\n\tnew_node.prev = current\n\tnew_node.next = current.next\n\tif current.next is not None:\n\t\tcurrent.next.prev = new_node\n\tcurrent.next = new_node\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tif head is None:\n\t\treturn head\n\tif head.data >= x:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\tcurr = head\n\twhile curr.next is not None:\n\t\tif curr.data > x:\n\t\t\ttemp.prev = curr.prev\n\t\t\tcurr.prev.next = temp\n\t\t\ttemp.next = curr\n\t\t\tcurr.prev = temp\n\t\t\treturn head\n\t\tcurr = curr.next\n\tif curr.data > x:\n\t\ttemp.prev = curr.prev\n\t\tcurr.prev.next = temp\n\t\ttemp.next = curr\n\t\tcurr.prev = temp\n\telse:\n\t\tcurr.next = temp\n\t\ttemp.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tptr = head\n\tlst = []\n\twhile ptr:\n\t\tlst.append(ptr.data)\n\t\tptr = ptr.next\n\ty = []\n\ti = 0\n\tflag = False\n\twhile i < len(lst):\n\t\tif lst[i] >= x and flag == False:\n\t\t\ty.append(x)\n\t\t\tflag = True\n\t\ty.append(lst[i])\n\t\ti += 1\n\tif flag == False:\n\t\ty.append(x)\n\tll = doublyLL()\n\ttail = None\n\tfor i in y:\n\t\ttail = ll.insert(tail, i)\n\treturn ll.head\n", "def sortedInsert(head, x):\n\tnew = Node(x)\n\tif x < head.data:\n\t\tnew.next = head\n\t\thead.prev = new\n\t\treturn new\n\tcurr = head\n\twhile curr and curr.next and (curr.next.data < x):\n\t\tcurr = curr.next\n\tnew.next = curr.next\n\tnew.prev = curr\n\tif curr.next:\n\t\tcurr.next.prev = new\n\tcurr.next = new\n\treturn head\n", "def sortedInsert(head, x):\n\tnewNode = Node(x)\n\tcurr = head\n\twhile curr.next and curr.next.data < x:\n\t\tcurr = curr.next\n\tif curr == head and curr.data >= x:\n\t\tnewNode.next = curr\n\t\tcurr.prev = newNode\n\t\treturn newNode\n\tif curr == head:\n\t\tnewNode.next = curr.next\n\t\tcurr.next.prev = newNode\n\t\tcurr.next = newNode\n\t\tnewNode.prev = curr\n\t\treturn head\n\telif curr.next == None:\n\t\tcurr.next = newNode\n\t\tnewNode.prev = curr\n\t\treturn head\n\tcurr.next.prev = newNode\n\tnewNode.next = curr.next\n\tcurr.next = newNode\n\tnewNode.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tnode = Node(x)\n\tif head == None:\n\t\treturn node\n\tif x < head.data or x == head.data:\n\t\tnode.next = head\n\t\thead.prev = node\n\t\thead = node\n\t\treturn head\n\tcurr = head\n\tprev = head\n\twhile curr:\n\t\tif x <= curr.data:\n\t\t\tnode.next = curr\n\t\t\tcurr.prev.next = node\n\t\t\tnode.prev = curr.prev\n\t\t\tcurr.prev = node\n\t\t\treturn head\n\t\telse:\n\t\t\tprev = curr\n\t\t\tcurr = curr.next\n\tprev.next = node\n\tnode.prev = prev\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = head\n\tnewnode = Node(x)\n\tif temp.data >= x:\n\t\tnewnode.next = temp\n\t\ttemp.prev = newnode\n\t\thead = newnode\n\t\treturn head\n\twhile temp.next.next:\n\t\tif temp.next.data >= x:\n\t\t\tbreak\n\t\ttemp = temp.next\n\tleftval = temp.next\n\tif leftval.data >= x:\n\t\ttemp.next = newnode\n\t\tnewnode.prev = temp\n\t\tnewnode.next = leftval\n\t\tleftval.prev = newnode\n\telse:\n\t\tleftval.next = newnode\n\t\tnewnode.prev = leftval\n\treturn head\n", "def sortedInsert(head, x):\n\tnode = Node(x)\n\tif head.data >= x:\n\t\thead.prev = node\n\t\tnode.next = head\n\t\treturn node\n\tcurr = head\n\tright = curr.next\n\twhile curr != None:\n\t\tif right == None:\n\t\t\tcurr.next = node\n\t\t\tnode.prev = curr\n\t\t\tbreak\n\t\tif curr.data <= x and right.data > x:\n\t\t\tnode.next = right\n\t\t\tnode.prev = curr\n\t\t\tcurr.next = node\n\t\t\tright.prev = node\n\t\t\tbreak\n\t\tcurr = right\n\t\tright = curr.next\n\treturn head\n", "def sortedInsert(head, x):\n\tn = Node(x)\n\tif head.data > n.data:\n\t\tn.next = head\n\t\thead.prev = n\n\t\thead = n\n\telse:\n\t\ttmp = head\n\t\tflg = 0\n\t\twhile tmp:\n\t\t\tif tmp.data > n.data:\n\t\t\t\tn.next = tmp\n\t\t\t\tn.prev = tmp.prev\n\t\t\t\tn.prev.next = n\n\t\t\t\ttmp.prev = n\n\t\t\t\tflg = 1\n\t\t\t\tbreak\n\t\t\ttmp = tmp.next\n\t\tif flg == 0:\n\t\t\ttmp = head\n\t\t\twhile tmp.next:\n\t\t\t\ttmp = tmp.next\n\t\t\ttmp.next = n\n\t\t\tn.prev = tmp\n\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\tcurr = head\n\tif head.data >= x:\n\t\tnew_node.next = head\n\t\tnew_node.prev = None\n\t\thead.prev = new_node\n\t\treturn new_node\n\twhile curr.next != None:\n\t\tif curr.next.data >= x:\n\t\t\ttemp = curr.next\n\t\t\tcurr.next = new_node\n\t\t\tnew_node.next = temp\n\t\t\tnew_node.prev = curr\n\t\t\ttemp.prev = new_node\n\t\t\treturn head\n\t\tcurr = curr.next\n\tif curr.data < x:\n\t\tnew_node.next = None\n\t\tnew_node.prev = curr\n\t\tcurr.next = new_node\n\t\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tc1 = head\n\tif head == None:\n\t\treturn temp\n\tif head.data > temp.data:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\tif head.next == None:\n\t\thead.next = temp\n\t\ttemp.prev = head\n\t\treturn head\n\twhile c1.next.data < temp.data:\n\t\tc1 = c1.next\n\t\tif c1.next == None:\n\t\t\tbreak\n\tif c1.next == None:\n\t\tc1.next = temp\n\t\ttemp.prev = c1\n\t\treturn head\n\telse:\n\t\ttemp.next = c1.next\n\t\tc1.next.prev = temp\n\t\ttemp.prev = c1\n\t\tc1.next = temp\n\t\treturn head\n", "def sortedInsert(head, x):\n\t(cur, tmp) = (head, Node(x))\n\tif cur.data > tmp.data:\n\t\t(cur.prev, tmp.next) = (tmp, cur)\n\t\treturn tmp\n\twhile cur.next:\n\t\tif cur.data <= tmp.data <= cur.next.data:\n\t\t\tbreak\n\t\tcur = cur.next\n\t(tmp.prev, tmp.next) = (cur, cur.next)\n\tcur.next = tmp\n\tif tmp.next != None:\n\t\ttmp.next.prev = tmp\n\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\tif head == None:\n\t\thead = new_node\n\t\treturn head\n\tif head.data > new_node.data:\n\t\tnew_node.next = head\n\t\thead.prev = new_node\n\t\thead = new_node\n\t\treturn head\n\tcurrent = head\n\twhile current != None:\n\t\tif current.data <= new_node.data and current.next == None:\n\t\t\tcurrent.next = new_node\n\t\t\tnew_node.prev = current\n\t\t\treturn head\n\t\tif current.data <= new_node.data <= current.next.data:\n\t\t\tnew_node.next = current.next\n\t\t\tcurrent.next.prev = new_node\n\t\t\tnew_node.prev = current\n\t\t\tcurrent.next = new_node\n\t\t\treturn head\n\t\tcurrent = current.next\n\treturn head\n", "def sortedInsert(head, x):\n\tnewnode = Node(x)\n\tif head.data > x:\n\t\thead.prev = newnode\n\t\tnewnode.next = head\n\t\thead = newnode\n\t\treturn head\n\tprev = head\n\ttemp = head.next\n\twhile temp != None:\n\t\tif temp.data > x:\n\t\t\ttempp = temp.prev\n\t\t\tnewnode.prev = temp.prev\n\t\t\tnewnode.next = temp\n\t\t\ttemp.prev = newnode\n\t\t\ttempp.next = newnode\n\t\t\treturn head\n\t\tprev = temp\n\t\ttemp = temp.next\n\tprev.next = newnode\n\tnewnode.prev = prev\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = head\n\tnew = Node(x)\n\tif temp.data >= x:\n\t\ttemp.prev = new\n\t\tnew.next = temp\n\t\thead = new\n\t\treturn head\n\twhile temp.next != None:\n\t\tif temp.data <= x and temp.next.data >= x:\n\t\t\ta = temp.next\n\t\t\tnew.prev = temp\n\t\t\tnew.next = a\n\t\t\ttemp.next = new\n\t\t\tnew.next.prev = new\n\t\t\treturn head\n\t\ttemp = temp.next\n\tif temp.data < x:\n\t\ttemp.next = new\n\t\tnew.prev = temp\n\t\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\tif head is None:\n\t\thead = new_node\n\t\treturn head\n\tif x < head.data:\n\t\tnew_node.next = head\n\t\thead.prev = new_node\n\t\thead = new_node\n\t\treturn head\n\tcurr = head\n\twhile curr.next is not None and curr.next.data < x:\n\t\tcurr = curr.next\n\tnew_node.next = curr.next\n\tnew_node.prev = curr\n\tif curr.next is not None:\n\t\tcurr.next.prev = new_node\n\tcurr.next = new_node\n\treturn head\n", "def sortedInsert(head, x):\n\tif head.data >= x:\n\t\tnode = Node(x)\n\t\thead.prev = node\n\t\tnode.next = head\n\t\treturn node\n\tstack = [head]\n\twhile len(stack) > 0:\n\t\tcurrent = stack.pop()\n\t\tif current.next:\n\t\t\tif current.next.data >= x:\n\t\t\t\tnode = Node(x)\n\t\t\t\tnode.next = current.next\n\t\t\t\tnode.prev = current\n\t\t\t\tcurrent.next.prev = node\n\t\t\t\tcurrent.next = node\n\t\t\t\treturn head\n\t\t\tstack.append(current.next)\n\t\telse:\n\t\t\tnode = Node(x)\n\t\t\tcurrent.next = node\n\t\t\tnode.prev = current\n\t\t\treturn head\n", "def sortedInsert(head, x):\n\telem = Node(x)\n\tif head == None:\n\t\thead = elem\n\tif head.next == None:\n\t\tif head.data > elem.data:\n\t\t\telem.next = head\n\t\t\thead.prev = elem\n\t\t\thead = elem\n\t\telse:\n\t\t\thead.next = elem\n\t\t\telem.prev = head\n\t\treturn head\n\tcurr = head\n\tflag = 'asc'\n\tif curr.data > curr.next.data:\n\t\tflag = 'desc'\n\tif flag == 'asc':\n\t\twhile curr.next != None and curr.next.data < elem.data:\n\t\t\tcurr = curr.next\n\telse:\n\t\twhile curr.next != None and curr.next.data > elem.data:\n\t\t\tcurr = curr.next\n\tif curr == head and curr.data > elem.data and (flag == 'asc'):\n\t\telem.next = head\n\t\thead.prev = elem\n\t\thead = elem\n\telif curr == head and curr.data < elem.data and (flag == 'desc'):\n\t\telem.next = head\n\t\thead.prev = elem\n\t\thead = elem\n\telse:\n\t\telem.next = curr.next\n\t\tif curr.next != None:\n\t\t\tcurr.next.prev = elem\n\t\telem.prev = curr\n\t\tcurr.next = elem\n\treturn head\n", "def sortedInsert(head, x):\n\tif head.data > x:\n\t\tnode = Node(x)\n\t\thead.prev = node\n\t\tnode.next = head\n\t\thead = node\n\t\treturn head\n\tcurr = head\n\twhile curr:\n\t\tif curr.data > x:\n\t\t\tprev = curr.prev\n\t\t\tnode = Node(x)\n\t\t\tprev.next = node\n\t\t\tnode.prev = prev\n\t\t\tnode.next = curr\n\t\t\tcurr.prev = node\n\t\t\treturn head\n\t\tif curr.next:\n\t\t\tcurr = curr.next\n\t\telse:\n\t\t\tbreak\n\tnode = Node(x)\n\tnode.prev = curr\n\tcurr.next = node\n\treturn head\n", "def sortedInsert(head, x):\n\ta = Node(x)\n\tp = head\n\twhile p != None:\n\t\tif head.data >= x:\n\t\t\ta.next = head\n\t\t\thead.prev = a\n\t\t\thead = a\n\t\t\treturn head\n\t\telif p.data <= x and p.next.data >= x:\n\t\t\ta.prev = p\n\t\t\tp.next.prev = a\n\t\t\ta.next = p.next\n\t\t\tp.next = a\n\t\t\tp = p.next\n\t\t\treturn head\n\t\telse:\n\t\t\tp = p.next\n\t\t\tif p.next == None:\n\t\t\t\tp.next = a\n\t\t\t\ta.prev = p\n\t\t\t\treturn head\n", "def sortedInsert(head, x):\n\tnewNode = Node(x)\n\ttemp = head\n\tif head is None:\n\t\treturn newNode\n\telif x < head.data:\n\t\tnewNode.prev = None\n\t\tnewNode.next = head\n\t\thead.prev = newNode\n\t\thead = newNode\n\t\treturn newNode\n\twhile temp.next != None and x > temp.next.data:\n\t\ttemp = temp.next\n\tif temp.next == None:\n\t\tnewNode.next = temp.next\n\t\tnewNode.prev = temp\n\t\ttemp.next = newNode\n\telse:\n\t\tnewNode.next = temp.next\n\t\tnewNode.prev = temp\n\t\tnewNode.next.prev = newNode\n\t\ttemp.next = newNode\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tif head.data > x:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\treturn temp\n\tcurr = head\n\twhile curr.next != None and curr.next.data < x:\n\t\tcurr = curr.next\n\tif curr.next != None:\n\t\tn = curr.next\n\t\tn.prev = temp\n\t\ttemp.next = n\n\t\tcurr.next = temp\n\t\ttemp.prev = curr\n\telse:\n\t\ttemp.next = curr.next\n\t\tcurr.next = temp\n\t\ttemp.prev = curr\n\treturn head\n", "def sortedInsert(head, x):\n\tcurr = head\n\tnew_node = Node(x)\n\tinserted = False\n\twhile curr:\n\t\tif curr == head:\n\t\t\tif x < curr.data:\n\t\t\t\tnew_node.next = head\n\t\t\t\thead.prev = new_node\n\t\t\t\thead = new_node\n\t\t\t\treturn head\n\t\telif x < curr.data:\n\t\t\tnew_node.next = curr\n\t\t\tnew_node.prev = curr.prev\n\t\t\tcurr.prev.next = new_node\n\t\t\tcurr.prev = new_node\n\t\t\treturn head\n\t\tif curr.next == None:\n\t\t\tcurr.next = new_node\n\t\t\tnew_node.prev = curr\n\t\t\treturn head\n\t\tcurr = curr.next\n", "def sortedInsert(head, x):\n\thead_c = head\n\tif x < head.data:\n\t\ttemp_node = Node(x)\n\t\ttemp_node.next = head\n\t\thead.prev = temp_node\n\t\treturn temp_node\n\twhile head.next != None:\n\t\tif head.next.data >= x:\n\t\t\tbreak\n\t\thead = head.next\n\ttmp_node = Node(x)\n\tif head.next == None:\n\t\thead.next = tmp_node\n\t\ttmp_node.prev = head\n\t\treturn head_c\n\ttmp_node.next = head.next\n\ttmp_node.prev = head\n\thead.next.prev = tmp_node\n\thead.next = tmp_node\n\treturn head_c\n", "def sortedInsert(head, x):\n\tcurr = head\n\tq = Node(x)\n\tif head.data > x:\n\t\tq.next = head\n\t\thead.prev = q\n\t\treturn q\n\twhile curr.next != None:\n\t\tcurr = curr.next\n\tif curr.data <= x:\n\t\tcurr.next = q\n\t\tq.prev = curr\n\t\treturn head\n\tcurr = head\n\tfast = head\n\twhile curr.data <= x:\n\t\tfast = curr\n\t\tcurr = curr.next\n\tq.next = curr\n\tcurr.prev = q\n\tq.prev = fast\n\tfast.next = q\n\treturn head\n", "class Node:\n\n\tdef __init__(self, data):\n\t\tself.data = data\n\t\tself.next = None\n\t\tself.prev = None\n\ndef sortedInsert(head, x):\n\tnewNode = Node(x)\n\tif not head:\n\t\thead = newNode\n\telif x <= head.data:\n\t\tnewNode.next = head\n\t\thead.prev = newNode\n\t\thead = newNode\n\telse:\n\t\tnode = head\n\t\twhile node.next and node.next.data < x:\n\t\t\tnode = node.next\n\t\tnewNode.next = node.next\n\t\tif node.next:\n\t\t\tnode.next.prev = newNode\n\t\tnode.next = newNode\n\t\tnewNode.prev = node\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = Node(x)\n\tcurr = head\n\tif curr == None:\n\t\treturn head\n\tif curr.next == None:\n\t\tif x < curr.data:\n\t\t\ttemp.next = head\n\t\t\ttemp.prev = None\n\t\t\treturn temp\n\t\telse:\n\t\t\thead.next = temp\n\t\t\ttemp.prev = head\n\t\t\treturn head\n\tif x < head.data:\n\t\tcurr.prev = temp\n\t\ttemp.next = curr\n\t\treturn temp\n\twhile curr != None and curr.next.data < x:\n\t\tcurr = curr.next\n\t\tif curr.next == None:\n\t\t\tbreak\n\tif curr.next != None:\n\t\ttemp.next = curr.next\n\t\tcurr.next.prev = temp\n\t\ttemp.prev = curr\n\t\tcurr.next = temp\n\t\treturn head\n\telif curr.next == None:\n\t\ttemp.next = None\n\t\tcurr.next = temp\n\t\ttemp.prev = curr\n\t\treturn head\n", "def sortedInsert(head, x):\n\tnewNode = Node(x)\n\tif not head:\n\t\thead = newNode\n\t\treturn head\n\telif head.data > x:\n\t\tnewNode.next = head\n\t\tnewNode.next.prev = newNode\n\t\thead = newNode\n\t\treturn head\n\telse:\n\t\tcurrNode = head\n\t\twhile currNode.next and currNode.next.data < x:\n\t\t\tcurrNode = currNode.next\n\t\tnewNode.next = currNode.next\n\t\tif currNode.next:\n\t\t\tcurrNode.next.prev = newNode\n\t\tcurrNode.next = newNode\n\t\tnewNode.prev = currNode\n\t\treturn head\n", "def sortedInsert(head, x):\n\tt = head\n\tk = Node(x)\n\tk.next = None\n\tk.prev = None\n\tif x <= t.data:\n\t\tk.next = t\n\t\tt.prev = k\n\t\thead = k\n\t\treturn head\n\twhile t.next != None:\n\t\th = t.next\n\t\tif x >= t.data and x <= t.next.data:\n\t\t\tt.next = k\n\t\t\tk.prev = t\n\t\t\tk.next = h\n\t\t\th.prev = k\n\t\t\treturn head\n\t\tt = t.next\n\tt.next = k\n\tk.prev = t\n\treturn head\n", "def sortedInsert(head, x):\n\tnew_node = Node(x)\n\ttemp_node = head\n\tif x <= head.data:\n\t\tnew_node.next = head\n\t\thead = new_node\n\t\ttemp_node.prev = new_node\n\telse:\n\t\tlast_node = head\n\t\twhile last_node.next is not None:\n\t\t\tlast_node = last_node.next\n\t\tif x >= last_node.data:\n\t\t\tlast_node.next = new_node\n\t\t\tnew_node.prev = last_node\n\t\telse:\n\t\t\twhile temp_node.next.data < x:\n\t\t\t\ttemp_node = temp_node.next\n\t\t\tnext_node = temp_node.next\n\t\t\ttemp_node.next = new_node\n\t\t\tnew_node.next = next_node\n\t\t\tnext_node.prev = new_node\n\t\t\tnew_node.prev = temp_node\n\treturn head\n", "def sortedInsert(head, x):\n\tcopyHead = head\n\twhile head and head.data < x:\n\t\tif not head.next:\n\t\t\tend = head\n\t\thead = head.next\n\tif not head:\n\t\tnewEnd = Node(x)\n\t\tend.next = newEnd\n\t\tnewEnd.prev = end\n\telif head.data >= x:\n\t\tnewNode = Node(x)\n\t\ttemp = head.prev\n\t\thead.prev = newNode\n\t\tnewNode.next = head\n\t\tif temp:\n\t\t\tnewNode.prev = temp\n\t\t\ttemp.next = newNode\n\t\telse:\n\t\t\treturn newNode\n\treturn copyHead\n", "def sortedInsert(head, x):\n\tif head.data > x:\n\t\tstart = Node(x)\n\t\tstart.next = head\n\t\thead.prev = start\n\t\treturn start\n\tstart = head\n\twhile head.next and head.next.data < x:\n\t\thead = head.next\n\ttemp = head.next\n\thead.next = Node(x)\n\thead.next.next = temp\n\thead.next.prev = head\n\tif temp:\n\t\ttemp.prev = head.next\n\treturn start\n", "def sortedInsert(head, x):\n\ttemp = head\n\tnode = Node(x)\n\tif head is None:\n\t\treturn head\n\tif head.data >= x:\n\t\ttemp.prev = node\n\t\tnode.next = temp\n\t\thead = node\n\t\treturn head\n\twhile temp.next is not None:\n\t\tif temp.next.data > x:\n\t\t\ttemp.next.prev = node\n\t\t\tnode.next = temp.next\n\t\t\tnode.prev = temp\n\t\t\ttemp.next = node\n\t\t\treturn head\n\t\ttemp = temp.next\n\ttemp.next = node\n\tnode.prev = temp\n\treturn head\n", "def sortedInsert(head, x):\n\ttemp = head\n\tN = Node(x)\n\tif head.data >= x:\n\t\tN.next = head\n\t\thead.prev = N\n\t\thead = N\n\t\treturn head\n\twhile temp.next:\n\t\tif temp.data <= x and temp.next.data >= x:\n\t\t\tt = temp.next\n\t\t\tN.next = temp.next\n\t\t\tN.prev = temp\n\t\t\ttemp.next = N\n\t\t\tt.prev = N\n\t\t\treturn head\n\t\ttemp = temp.next\n\ttemp.next = N\n\tN.prev = temp\n\treturn head\n", "def sortedInsert(head, x):\n\tnode = Node(x)\n\tif x < head.data:\n\t\t(node.next, head.prev) = (head, node)\n\t\treturn node\n\tcur = head\n\twhile cur.next and cur.next.data < x:\n\t\tcur = cur.next\n\tif cur.next is None:\n\t\t(cur.next, node.prev) = (node, cur)\n\telse:\n\t\tnxt = cur.next\n\t\tcur.next = node\n\t\tnode.prev = cur\n\t\tnode.next = nxt\n\t\tnxt.prev = node\n\treturn head\n", "def sortedInsert(head, x):\n\tc = 0\n\tcurr = head\n\ttemp = Node(x)\n\tif temp.data < head.data:\n\t\ttemp.next = head\n\t\thead.prev = temp\n\t\ttemp.prev = None\n\t\thead = temp\n\t\treturn head\n\telif n == 1:\n\t\thead.next = temp\n\t\ttemp.prev = head\n\t\ttemp.next = None\n\t\treturn head\n\telse:\n\t\twhile curr.next is not None:\n\t\t\tif curr.data <= x and curr.next.data > x:\n\t\t\t\ta = curr.next\n\t\t\t\tcurr.next = temp\n\t\t\t\ttemp.prev = curr\n\t\t\t\ttemp.next = a\n\t\t\t\ta.prev = temp\n\t\t\t\tbreak\n\t\t\tcurr = curr.next\n\t\tif curr.data < x and curr.next == None:\n\t\t\tcurr.next = temp\n\t\t\ttemp.prev = curr\n\t\t\ttemp.next = None\n\t\treturn head\n"]

starter_code:
#User function Template for python3

'''

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

        self.prev = None

'''

def sortedInsert(head, x):

    #code here

input_output: {"inputs": ["LinkedList:\r\n\r\nX = 9"], "outputs": [""]}

difficulty: EASY

raw_tags: ['Data Structures', 'doubly-linked-list', 'Linked List']

source: geekforgeeks

skill_types: ['Data structures']

raw_problem:
Given a sorted doubly linked list and an element X, your need to insert the element X into correct position in the sorted DLL.

Example:

Input:
LinkedList:

X = 9
Output:

Your Task:

You only need to complete the function sortedInsert() that takes head reference and x as arguments and returns the head of the modified list. The printing and checking tasks are done by the driver code.

Expected Time Complexity: O(n).

Expected Auxiliary Space: O(1).

Constraints:

1 <= Number of nodes <= 103

question:
Given a sorted doubly linked list and an element X, your need to insert the element X into correct position in the sorted DLL.
Example:

Input:
LinkedList:
![image](1.png)
X = 9
Output:
![image](2.png)

Your Task:
You only need to complete the function sortedInsert() that takes head reference and x as arguments and returns the head of the modified list. The printing and checking tasks are done by the driver code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Number of nodes <= 10^{3}

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test