#------------------------------------------
def somme(l,k):
    s = 0
    for i in range(len(l)):
        s = s + l[i] ** k
    return s

def chiffres(n):
    s = str(n)
    #interprétation 1 : liste d'entiers
    l=[]
    for i in range(len(s)):
        l.append(int(s[i]))
    return l
    
def chiffres(n):
    s = str(n)   
    #interprétation 2 : liste de caractères, mais pas pratique pour faire des calculs
    return s

# avec l'interprétation 1
def arm(n,k):
    c = chiffres(n)
    return somme(c,k) == n
    
def arms(n,k):
    l = []
    for i in range(n+1):
        if arm(i,k):
            l.append(i)
    return l
    
#------------------------------------------
def ordonnee(L):
    n = len(L)
    i = 0
    while i < n-1 and L[i] <= L[i+1] :
        i = i + 1
    return (i >= n-1)
    
def fusion(L,M):
    l = len(L)
    m = len(M)
    if not( ordonnee(L) and ordonnee(M)):
        return False
    i = 0
    j = 0
    N = []
    #tant que les deux listes ne sont pas épuisées, on prend le plus petit des deux qui restent à choisir
    while i < l and j < m:
        if L[i] <= M[j]:
            N.append(L[i])
            i = i + 1
        else:
            N.append(M[j])
            j = j + 1
    #quand c'est fini, l'une des deux listes est reversée dans N, il suffit d'y ajouter les éléments de l'autre
    if i == l:
        N.extend(M[j:])
		#OU code équivalent
        for k in range(j,m):
			N.append(M[k])
    else:
        N.extend(L[i:])
		#OU code équivalent
        for k in range(i,l):
			N.append(L[k])
    return N
    
#------------------------------------------
def melange(L):
    M = []
    N = []
    n = len(L)
    for i in range(n):
        if i % 2 == 0:
            M.append(L[i])
        else:
            N.append(L[i])
    return M + N

def periode(L):
    M = melange(L)
    k = 1
    while M != L:
        M = melange(M)
        k = k + 1
    return k

# fonction annexe
def rep(n):
    L = []
    for i in range(1,n+1):
        L.append(i)
    return L

def rapportmax(n):
    m = 0
    j = 0
    L = []
    for i in range(2,n+1):
        M = rep(i)
        k = periode(M)
        L.append(k/i)
        if k/i > m :
            m = k/i
            j = i
    return j

#------------------------------------------
def enligne(n):
    if n % 3 == 0:
        k = (n) // 3
        l = k
    elif n % 3 == 1:
        k = (n) // 3 + 1 
        l = k - 1
    else:
        k = (n) // 3 +1
        l = k
    L = []
    # les lignes communes
    for i in range((n) // 3):
        L.append([i, i+k, i+k+l])
    # les deux cas particuliers avec la petite ligne en plus
    if n % 3 == 1:
        L.append([k-1])
    elif n % 3 == 2:
        L.append([k-1,k+l-1])
    return L
    
def Enligne(n,p):
    l = n // p
    incr = []
    r = n % p
    for i in range(p-1):
        if i < r:
            incr.append((i+1) * (l+1))
        else:
            incr.append((r+1) * (l+1) + (i-r) * l - 1 )
    L = []
    # les lignes communes
    for i in range(l):
        ligne = [i]
        for j in range(p-1):
            ligne.append(i + incr[j])
        L.append(ligne)
    # la petite ligne en plus éventuelle
    ligne = L[l-1][:r]
    for j in range(r):
        ligne[j] = ligne[j] + 1
    if ligne != []:
        L.append(ligne)
    return L