Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
V,E = map(int, input().split())
#??£??\??????????????????
A = [[] for i in range(V)]
for i in range(E):
    s,t = map(int, input().split())
    A[s].append(t)
    A[t].append(s)
    
#?????????????¨???????
prenum = [None for i in range(V)]
#DFS???????????????????????????
parent = [None for i in range(V)]
#????????????????°??????????
lowest = [None for i in range(V)]
#?¨????????????°??????
visited = [False for i in range(V)]

def DFS(u = 0, prev = -1, timer = 0):
    prenum[u] = timer
    lowest[u] = timer
    timer += 1
    visited[u] = True
    
    for v in A[u]:
        if not visited[v]:
            parent[v] = u
            DFS(v, u, timer)
            lowest[u] = min(lowest[u], lowest[v])
        elif v != prev:
            lowest[u] = min(lowest[u], prenum[v])
DFS()

ans = set()
 
for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)
 
if parent.count(0) >= 2:
    ans.add(0)
else:
    ans.discard(0)
 
ans = list(ans)
ans.sort()
 
if ans:
    print(*ans, sep = '\n')

Fixed submission:
import sys
sys.setrecursionlimit(100000)

V,E = map(int, input().split())
#???£??\??????????????????
A = [[] for i in range(V)]
for i in range(E):
    s,t = map(int, input().split())
    A[s].append(t)
    A[t].append(s)
     
#??????????????¨???????
prenum = [None for i in range(V)]
#DFS???????????????????????????
parent = [None for i in range(V)]
#?????????????????°??????????
lowest = [None for i in range(V)]
#??¨?????????????°??????
visited = [False for i in range(V)]
 
def DFS(u = 0, prev = -1, timer = 0):
    prenum[u] = timer
    lowest[u] = timer
    timer += 1
    visited[u] = True
     
    for v in A[u]:
        if not visited[v]:
            parent[v] = u
            DFS(v, u, timer)
            lowest[u] = min(lowest[u], lowest[v])
        elif v != prev:
            lowest[u] = min(lowest[u], prenum[v])
DFS()
 
ans = set()
  
for u in range(1, V):
    p = parent[u]
    if prenum[p] <= lowest[u]:
        ans.add(p)
  
if parent.count(0) >= 2:
    ans.add(0)
else:
    ans.discard(0)
  
ans = list(ans)
ans.sort()
  
if ans:
    print(*ans, sep = '\n')
Buggy python submission (verdict: Runtime Error):
import heapq as pq
inf = float("inf")
n,e = map(int, input().split())
M = [[] for i in range(n)]
L = list(map(int, range(n)))

for i in range(e):
    s,t = map(int, input().split())
    M[s].append(t)
    if t in L:
        L.remove(t)
  
def dijkstra(s):
    color = [0] * n    
    H =[]
    pq.heappush(H, s)
    while len(H) != 0:
        u1 = pq.heappop(H)
        for v1 in M[u1]:
            if v1 and color[v1] == 1:
                print("1")
                return False
            else:
                color[u1] = 1
                pq.heappush(H, v1)
    return True

if not L:
    print("1")
for i in L:
    flag = False
    if dijkstra(i):
        flag = dijkstra(i)
    else: break

if flag:
    print("0")

Fixed submission:
import heapq as pq
inf = float("inf")
n,e = map(int, input().split())
M = [[] for i in range(n)]

for i in range(e):
    s,t = map(int, input().split())
    M[s].append(t)

def dfs(s):
    if not visit[s]:
        visit[s] = True
        stack[s] = True
        for t in M[s]:
            if stack[t]:
                print(1)
                exit()
            else: dfs(t)
    stack[s] = False

visit = [False for _ in range(n)]
stack = [False for _ in range(n)]
for i in range(n):
    dfs(i)
print("0")
Buggy python submission (verdict: Runtime Error):
import math

def hensa(n, S):
 m = sum(S)/n
 x = 0
 for i in S:
  x += (i - m) ** 2
 hensa = math.sqrt(x / n)
 return hensa

n = 1
while n != 0:
 n = int(input())
 S = list(map(int, input().split()))
 print("{0:04f}".format(hensa(n, S)))

Fixed submission:
import math

def hensa(n, S):
 m = sum(S)/n
 x = 0
 for i in S:
  x += (i - m) ** 2
 hensa = math.sqrt(x / n)
 return hensa

n = int(input())
while n != 0:
 S = list(map(int, input().split()))
 print("{0:04f}".format(hensa(n, S)))
 n = int(input())
Buggy python submission (verdict: Runtime Error):
x,y = map(int, input()split())
S = X * y
L = 2 * (x + y)
print(S + " " + L)

Fixed submission:
a,b = map(int, input().split())
S = a * b
L = 2 * (a + b)
print(str(S) + " " + str(L))

Buggy python submission (verdict: Runtime Error):
x,y = map(int, input().split())
S = X * y
L = 2 * (x + y)
print(S + " " + L)
 

Fixed submission:
a,b = map(int, input().split())
S = a * b
L = 2 * (a + b)
print(str(S) + " " + str(L))
Buggy python submission (verdict: Runtime Error):
S = input()
h = S // 3600
ms = S % 3600
m = ms // 60
s = ms % 60
print(h + ":" + m + ":" + s)

Fixed submission:
S = int(input())
s = str(S % 60)
HM = S // 60
m = str(HM % 60)
h = str(HM // 60)
print(h + ":" + m + ":" + s)

Buggy python submission (verdict: Runtime Error):
S = int(input())
h = S // 3600
ms = S % 3600
m = ms // 60
s = ms % 60
print(h + ":" + m + ":" + s)
 

Fixed submission:
S = int(input())
s = str(S % 60)
HM = S // 60
m = str(HM % 60)
h = str(HM // 60)
print(h + ":" + m + ":" + s)

Buggy python submission (verdict: Runtime Error):
S = int(input())
h = S // 3600
ms = S % 3600
m = ms // 60
s = ms % 60
print(h + ":" + m + ":" + s)

Fixed submission:
S = int(input())
s = str(S % 60)
HM = S // 60
m = str(HM % 60)
h = str(HM // 60)
print(h + ":" + m + ":" + s)
Buggy python submission (verdict: Runtime Error):

W,H,x,y,r = map(int, input().split())

if r <= x and x <= W and r <= y and y <= H:
 print(Yes)
else:
 print(No)

Fixed submission:
W,H,x,y,r = map(int, input().split())
   
if r <= x and x <= W - r and r <= y and y <= H - r:
 print('Yes')
else:
 print('No')
Buggy python submission (verdict: Runtime Error):
import math
r = int(input())

S = r ** 2 * math.pi
R = 2 * r * math.pi
print("{0:.6f}".format(S) + " " + "{0:.6f}".format(R))

Fixed submission:
import math
r = float(input())
 
S = r ** 2 * math.pi
R = 2 * r * math.pi
print("{0:.6f}".format(S) + " " + "{0:.6f}".format(R))
Buggy python submission (verdict: Runtime Error):
def dynamic(n):
    if n == 0 or n == 1:
        return 1
    if F[n] != 0:
        return F[n]
    F[n] = dynamic(n - 1) + dynamic(n - 2)
    return F[n]

if __name__ == '__main__':
    n = int(raw_input())
    print(dynamic(n))

Fixed submission:
N = 44
F = [0]*(N+1)

def dynamic(n):
    if n == 0 or n == 1:
        return 1
    if F[n] != 0:
        return F[n]
    F[n] = dynamic(n - 1) + dynamic(n - 2)
    return F[n]

if __name__ == '__main__':
    n = int(raw_input())
    print(dynamic(n))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python

n = int(input())

def fib(n):
    l = [0] * (n+1)
    l[0] = 1
    l[1] = 1

    for i in range(2, n+1):
        l[i] = l[i-1] + l[i-2]

    return l[i]

print(fib(n))

Fixed submission:
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

    for i in range(2, n+1):
        l.append(l[i-1] + l[i-2])

    return l[-1]

print(fib(n))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python

n = int(input())

def fib(n):
    l = [0] * (n+1)
    l[0] = 1
    l[1] = 1

    for i in range(2, n+1):
        l[i] = l[i-1] + l[i-2]

    return l[i]

print(fib(n))

Fixed submission:
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

    for i in range(2, n+1):
        l.append(l[i-1] + l[i-2])

    return l[-1]

print(fib(n))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python

n = int(input())

def fib(n):
    l = [0] * (n+1)
    l[0] = 1
    l[1] = 1

    for i in range(2, n+1):
        l[i] = l[i-1] + l[i-2]

    return l[i]

print(fib(n))

Fixed submission:
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

    for i in range(2, n+1):
        l.append(l[i-1] + l[i-2])

    return l[-1]

print(fib(n))

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

    for i in range(2, n+1):
        l.append(l[i-1] + l[i-2])

    return l[i]

print(fib(n))

Fixed submission:
#!/usr/bin/python

n = int(input())

def fib(n):
    l = list()
    l.append(1)
    l.append(1)

    for i in range(2, n+1):
        l.append(l[i-1] + l[i-2])

    return l[-1]

print(fib(n))
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
dp = [[0] * W for _ in range(N+1)]
weights = list()
values = list()
for _ in range(N):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

for i in range(N):
    for w in range(W):
        if w >= weights[i]: 
            dp[i+1][w] = max(dp[i][w-weights[i]] + values[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[n][W])


Fixed submission:
N, W = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N)]
weights = list() 
values = list() 
for _ in range(N):
    v, w = map(int, input().split())
    values.append(v)
    weights.append(w)

for n in range(N):
    for w in range(1, W+1):
        if n == 0 and w >= weights[n]:
            dp[n][w] = values[n]
        elif w >= weights[n]: 
            dp[n][w] = max(dp[n-1][w-weights[n]] + values[n], dp[n-1][w])
        else:
            dp[n][w] = dp[n-1][w]
print(dp[N-1][W])
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Fri Jun 16 18:45:04 2017

@author: syaga
"""

if __name__ == "__main__":
    n = int(input())
    a = []
    for i in range(n):
        a.append(int(input()))
    max = a[1] - a[0]
    for i in range(1, len(a)):
        for j in range(0, i):
            diff = a[i] - a[j]
            if diff > max:
                max = diff
    print(max)

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Fri Jun 16 18:45:04 2017

@author: syaga
"""

if __name__ == "__main__":
    n = int(input())
    a = []
    for i in range(n):
        a.append(int(input()))
    max = a[1] - a[0]
    mini = a[0]
    for i in range(1, len(a)):
        diff = a[i] - mini
        if diff > max:
            max = diff
        if mini > a[i]:
            mini = a[i]
    print(max)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 18 10:42:00 2017

@author: syaga
"""

import math

def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i-g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt
         
def shellSort(A, n):
    cnt = 0
    m = int(math.log(n-1,4)) + 1
    print(m)
    G = [4**i for i in range(m-1, -1, -1)]
    print(" ".join(map(str, G)))
    for i in range(0, m):
        cnt = insertionSort(A, n, G[i], cnt)
    print(cnt)

if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        A.append(int(input()))
    shellSort(A, n)
    for i in A:
        print(i)

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 18 10:42:00 2017

@author: syaga
"""

import math

def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i-g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt
         
def shellSort(A, n):
    cnt = 0
    G = [1]
    if n != 1:
        for i in range(99):
            G.append(G[i]*3+1)
        G = [x for x in G if x < n]
        G.reverse()
    m = len(G)
    print(m)
    print(" ".join(map(str, G)))
    for i in range(0, m):
        cnt = insertionSort(A, n, G[i], cnt)
    print(cnt)

if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        A.append(int(input()))
    shellSort(A, n)
    for i in A:
        print(i)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    flag = 0
    while True:
        if flag == 1:
            break
        for i in range(len(a)):
            if a[i] == []:
                continue
            if a[i][1] <= q:
                time += a[i][1]
                ans.append([a[i][0], time])
                a[i] = []
                if len(ans) == len(a):
                    flag = 1
                    break
            else:
                a[i][1] -= q
                time += q
    for i in ans:
        print(" ".join(map(str, i)))

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    while len(a) != 0:
        x = a.pop(0)
        if x[1] <= q:
            time += x[1]
            ans.append([x[0], time])
        else:
            x[1] -= q
            time += q
            a.append(x)
    for i in ans:
        print(" ".join(map(str, i)))

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    flag = 0
    while True:
        if flag == 1:
            break
        for i in range(len(a)):
            if a[i] == []:
                continue
            if a[i][1] <= q:
                time += a[i][1]
                ans.append([a[i][0], time])
                a[i] = []
                if len(ans) == len(a):
                    flag = 1
                    break
            else:
                a[i][1] -= q
                time += q
    for i in ans:
        print(" ".join(map(str, i)))

Fixed submission:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    while len(a) != 0:
        x = a.pop(0)
        if x[1] <= q:
            time += x[1]
            ans.append([x[0], time])
        else:
            x[1] -= q
            time += q
            a.append(x)
    for i in ans:
        print(" ".join(map(str, i)))
Buggy python submission (verdict: Runtime Error):
def binary_search(S, a):
    leng = len(S)
    mid = leng // 2
    if S[mid] == a:
        return True
    elif leng < 2:
        return False
    elif S[mid] < a:
        return binary_search(S[mid+1:], a)
    else:
        return binary_search(S[:mid], a)
        
if __name__=="__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))
    ans = 0
    for i in T:
        if binary_search(S, i):
            ans += 1
    print(ans)

Fixed submission:
def binary_search(S, t):
    start = 0
    end = len(S)
    while True:
        mid = start + (end-start)//2
        if S[mid] == t:
            return True
        elif (end-start) < 2:
            return False
        elif S[mid] < t:
            start = mid
        else:
            end = mid

if __name__ == "__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))
    ans = 0
    for i in T:
        if binary_search(S, i):
            ans += 1
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    inp = sys.stdin.readlines()
    lis = []
    for i in range(n):
        com = inp[i].split()
        if com[0] == "insert":
            lis.append(com[1])
        elif com[1] in lis:
            print("yes")
        else:
            print("no")

Fixed submission:
import sys

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    inp = sys.stdin.readlines()
    lis = set()
    for i in range(n):
        com = inp[i].split()
        if com[0] == "insert":
            lis.add(com[1])
        elif com[1] in lis:
            print("yes")
        else:
            print("no")
Buggy python submission (verdict: Time Limit Exceeded):
def solve(i, m):
    if m == 0:
        return True
    if i == n:
        return False
    return solve(i+1, m) or solve(i+1, m-A[i])


if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    for m in M:
        if solve(0, m):
            print("yes")
        else:
            print("no")

Fixed submission:
import itertools


def rev(x):
    return sumA - x


if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = list(map(int, input().split()))
    sumA = sum(A)
    all_sum = set()
    for i in range((n+1)//2):
        com = set(itertools.combinations(A, i+1))
        com_sum = set(map(sum, com))
        com_sum_rev = set(map(rev, com_sum))
        all_sum = all_sum.union(com_sum)
        all_sum = all_sum.union(com_sum_rev)
    for m in M:
        if m in all_sum:
            print("yes")
        else:
            print("no")
Buggy python submission (verdict: Runtime Error):
def CountingSort(A, B, k):
    C = [0 for i in range(k+2)]
    
    for j in range(n):
        C[A[j]] += 1
        
    for i in range(k+1):
        C[i] += C[i-1]
        
    for j in range(n-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1

if __name__=="__main__":
    n = int(input())
    D = list(map(int, input().split()))
    l = max(D)
    E = D[:]
    CountingSort(D, E, l)
    print(" ".join(map, str(E))))

Fixed submission:
def CountingSort(A, B, k):
    C = [0 for i in range(k+2)]
    
    for j in range(n):
        C[A[j]] += 1
        
    for i in range(k+1):
        C[i] += C[i-1]
        
    for j in range(n-1, -1, -1):
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1

if __name__=="__main__":
    n = int(input())
    D = list(map(int, input().split()))
    l = max(D)
    E = D[:]
    CountingSort(D, E, l)
    print(" ".join(map(str, E)))
Buggy python submission (verdict: Runtime Error):
def print_heap():
    for i in range(n):
        if (i-1)//2 in range(n):
            if 2*i+1 in range(n):
                if 2*1+2 in range(n):
                    print("node {}: key = {}, parent key = {}, left key = {}, right key = {},"
                          .format(i+1, heap[i], heap[(i-1)//2], heap[2*i+1], heap[2*i+2]))
                else:
                    print("node {}: key = {}, parent key = {}, left key = {},"
                          .format(i+1, heap[i], heap[(i-1)//2], heap[2*i+1]))
            else:
                print("node {}: key = {}, parent key = {},"
                      .format(i+1, heap[i], heap[(i-1)//2]))
        else:
            if 2*i+1 in range(n):
                if 2*1+2 in range(n):
                    print("node {}: key = {}, left key = {}, right key = {},"
                          .format(i+1, heap[i], heap[2*i+1], heap[2*i+2]))
                else:
                    print("node {}: key = {}, left key = {},"
                          .format(i+1, heap[i], heap[2*i+1]))
            else:
                print("node {}: key = {},".format(i+1, heap[i]))


if __name__ == "__main__":
    n = int(input())
    heap = list(map(int, input().split()))
    print_heap()

Fixed submission:
def print_heap():
    for i in range(n):
        if (i-1)//2 in range(n):
            if 2*i+1 in range(n):
                if 2*i+2 in range(n):
                    print("node {}: key = {}, parent key = {}, left key = {}, right key = {}, "
                          .format(i+1, heap[i], heap[(i-1)//2], heap[2*i+1], heap[2*i+2]))
                else:
                    print("node {}: key = {}, parent key = {}, left key = {}, "
                          .format(i+1, heap[i], heap[(i-1)//2], heap[2*i+1]))
            else:
                print("node {}: key = {}, parent key = {}, "
                      .format(i+1, heap[i], heap[(i-1)//2]))
        else:
            if 2*i+1 in range(n):
                if 2*i+2 in range(n):
                    print("node {}: key = {}, left key = {}, right key = {}, "
                          .format(i+1, heap[i], heap[2*i+1], heap[2*i+2]))
                else:
                    print("node {}: key = {}, left key = {}, "
                          .format(i+1, heap[i], heap[2*i+1]))
            else:
                print("node {}: key = {}, ".format(i+1, heap[i]))


if __name__ == "__main__":
    n = int(input())
    heap = list(map(int, input().split()))
    print_heap()
Buggy python submission (verdict: Runtime Error):
N = input()
A = map(int,raw_input().split())

for i in range(N-1):
        print A[i],
    print A[-1]

for i in range(1,N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    for i in range(N-1):
        print A[i],
    print A[-1]

Fixed submission:
N = input()
A = map(int,raw_input().split())

for i in range(N-1):
    print A[i],
print A[-1]

for i in range(1,N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    for i in range(N-1):
        print A[i],
    print A[-1]
Buggy python submission (verdict: Runtime Error):
N = input()
A = map(str,raw_input().split())
Ab = A[:]
As = A[:]

def BubbleSort(A,N):
    for i in range(N):
        flag = 0
        for i in range(1,N):
            j = N - i
            if A[j][1] < A[j-1][1]:
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
                flag = 1

def SelectionSort(A,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j][1] < A[minj][1]:
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v

def Output(A):
    for i in range(N-1):
        print A[i],
    print A[-1]

def Stable(AA):
    l = [AA[i] for i in range(N-1) if AA[i][1] == AA[i+1][1]]
    for item in l:
        for i in range(N-1):
            if A[i][1] == item[1]:
                if A[i] == item:
                    msg = "Stable"
                    break
                else:
                    msg = "Not stable"
                    break
    print msg

SelectionSort(As,N)
BubbleSort(Ab,N)

Output(Ab)
Stable(Ab)
Output(As)
Stable(As)

Fixed submission:
N = input()
A = map(str,raw_input().split())
Ab = A[:]
As = A[:]

def BubbleSort(A,N):
    for i in range(N):
        flag = 0
        for i in range(1,N):
            j = N - i
            if A[j][1] < A[j-1][1]:
                v = A[j]
                A[j] = A[j-1]
                A[j-1] = v
                flag = 1

def SelectionSort(A,N):
    for i in range(N):
        minj = i
        for j in range(i,N):
            if A[j][1] < A[minj][1]:
                minj = j
        v = A[i]
        A[i] = A[minj]
        A[minj] = v

def Output(A):
    for i in range(N-1):
        print A[i],
    print A[-1]

def Stable(AA):
    n = []
    for i in range(N-1):
        if AA[i][1] == AA[i+1][1] and AA[i][1] not in n:
            n.append(AA[i][1])
    l = []
    m = []
    for item in n:
        for i in range(N):
            if AA[i][1] == item:
                l.append(AA[i])
            if A[i][1] == item:
                m.append(A[i])
    if l == m:
        msg = "Stable"
    else:
        msg = "Not stable"
    print msg

SelectionSort(As,N)
BubbleSort(Ab,N)

Output(Ab)
Stable(Ab)
Output(As)
Stable(As)