Theatre Square in the capital city of Berland has a rectangular shape with the size *n* × *m* meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size *a* × *a*.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.
The input contains three positive integer numbers in the first line: *n*,  *m* and *a* (1 ≤  *n*, *m*, *a* ≤ 10<sup class="upper-index">9</sup>).
6 6 4
4
1 1 1
1
2 1 1
2
1 2 1
2
2 2 1
4
2 1 2
1
1 1 3
1
2 3 4
1
1000000000 1000000000 1
1000000000000000000
12 13 4
12
222 332 5
3015
1000 1000 10
10000
1001 1000 10
10100
100 10001 1000000000
1
1000000000 1000000000 1000000000
1
1000000000 1000000000 999999999
4
1000000000 1000000000 192
27126743055556
1000000000 987654321 1
987654321000000000
456784567 1000000000 51
175618850864484
39916800 134217728 40320
3295710
import numpy as np
import copy
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

import random
nbEntites = 100
nbLignes = 100
nbColones = 100
nbEtappes =100
tailleChamp = nbLignes*nbColones






def afficher(x, y, mouvX, mouvY, temps):

    print(x)
    print(y)
    print(len(x))
    fig, ax = plt.subplots()

    ax.set_xlim([0,nbColones])
    ax.set_ylim([0,nbLignes])
    bha = plt.scatter(x, y, s=10, c="red", )

    for gen in range(nbEtappes):
        bha.remove()

        colors = [((reseaux[i][1][0]+4)/8, (reseaux[i][2][0]+4)/8, (reseaux[i][3][0]+4)/8) for i in range(nbEntites)]
        bha = ax.scatter(x, y, s=10, c=colors)

        for numEntite in range(nbEntites):
            if (x[numEntite]+ mouvX[gen][numEntite])<=nbColones and (x[numEntite]+ mouvX[gen][numEntite])>=0:
                x[numEntite] = (x[numEntite]+ mouvX[gen][numEntite])
            if (y[numEntite] + mouvY[gen][numEntite])<=nbLignes and (y[numEntite] + mouvY[gen][numEntite])>=0:
                y[numEntite] = (y[numEntite] + mouvY[gen][numEntite])


        plt.title(str(gen))
        plt.draw()
        plt.pause(temps/nbEtappes)
    xy  = (nbLignes/4, nbColones/4)
    w = nbLignes/2
    h = nbColones/2

    rect = Rectangle(xy, w, h, color="green", alpha = 1/3)

    ax.add_patch(rect)

    plt.show()






xDepart = []
yDepart = []

pos = [[random.randint(0, nbLignes-1),random.randint(0, nbColones-1)] for i in range(nbEntites)]
for coord in pos:
    xDepart.append(coord[1])
    yDepart.append(coord[0])


plateau = []
for i in range(nbLignes):
    plateau.append([""]*nbColones)




for i in range(len(pos)):
    coord = pos[i]
    while plateau[coord[0]][coord[1]] !=  "":
        coord = [random.randint(0, nbLignes-1),random.randint(0, nbColones-1)]
    plateau[coord[0]][coord[1]] =  i

mouvX = []
mouvY = []
mouvX.append([0]*nbEntites)
mouvY.append([0]*nbEntites)


print(plateau)

#neurones input


def densite(num):
    d = 0
    case = [pos[num][0], pos[num][1]]
    aTester = [[case[0]-1, case[1]-1], [case[0]-1, case[1]], [case[0]-1, case[1]+1],
               [case[0], case[1] - 1],[case[0], case[1]],[case[0], case[1] + 1],
               [case[0] +1, case[1] - 1], [case[0]+1, case[1]], [case[0] +1,  case[1] + 1]]
    for case in aTester:
        if case[0]>=0 and case[0]<nbLignes and case[1]>=0 and case[1]<nbColones :
            if plateau[case[0]][case[1]]== "":
                pass
            else:
                d+=1
    return d/4.5-1


def mvtPossibles(num):
    liste = []
    case = [pos[num][0], pos[num][1]]
    aTester = [[case[0] - 1, case[1] - 1], [case[0] - 1, case[1]], [case[0] - 1, case[1] + 1],
               [case[0], case[1] - 1], [case[0], case[1] + 1],
               [case[0] + 1, case[1] - 1], [case[0] + 1, case[1]], [case[0] + 1, case[1] + 1]]
    mvt = [[- 1, - 1], [- 1, 0], [- 1,   1], [0,  - 1], [0, 1], [ 1, - 1], [ 1, 0], [1, 1  ]]
    i = 0
    for case in aTester:
        if case[0] >= 0 and case[0] < nbLignes and case[1] >= 0 and case[1] < nbColones:
            if plateau[case[0]][case[1]] == "":
                liste.append(mvt[i])
        i+=1
    return liste



def posX(num):
    return (pos[num][1]/(nbColones))*2-1

def posY(num):

    return (((nbLignes-1)-pos[num][0])/(nbLignes))*2-1

def mouvRnd(num):

    global mouvY
    global mouvX

    mvt = random.randint(0, 3)
    if mvt == 0:
        mouvHaut(num)
    elif mvt == 1:
        mouvGauche(num)
    elif mvt == 2:
        mouvDroite(num)
    else:
        mouvHaut(num)

def mouvHaut(num):

    global mouvY
    global mouvX

    if  pos[num][0] - 1>=0 :
         mouvY[-1][num] -=1

def mouvGauche(num):

    global mouvY
    global mouvX


    if pos[num][1]-1>=0:
        mouvX[-1][num] -= 1



def mouvDroite(num):

    global mouvY
    global mouvX

    #if pos[num][1] + 1 <nbColones:
    mouvX[-1][num] += 1



def mouvBas(num):

    global mouvY
    global mouvX

    if pos[num][0]+1<nbLignes:

        mouvY[-1][num] +=1



reseaux = []

def genTypesInput():
    return random.sample([0, 1, 2], 2)

def genTypesOutput():

    return random.sample([0, 1, 2, 3, 4], 3)

def GenReseauNeurone():
    typesInput = genTypesInput()
    depI1 = [random.uniform(-4, 4), random.uniform(-4, 4)]
    depI2 = [random.uniform(-4, 4), random.uniform(-4, 4)]
    depN1 = [random.uniform(-4, 4), random.uniform(-4, 4), random.uniform(-4, 4)]
    depN2 = [random.uniform(-4, 4), random.uniform(-4, 4), random.uniform(-4, 4)]
    constantes = [random.uniform(-1, 1), random.uniform(-1, 1) , random.uniform(-1, 1), random.uniform(-1, 1),random.uniform(-1, 1) ]

    typesOutput  = genTypesOutput()
    return [typesInput, depI1, depI2, depN1, depN2 , constantes, typesOutput]

for i in range(nbEntites):
    reseaux.append(GenReseauNeurone())

def calculInput(num, typesInput):
    val = []
    for i in range(2):
        if typesInput[i]==0:
            val.append(densite(num))
        elif typesInput[i]==1:
            val.append(posX(num))
        else:
            val.append(posY(num))
    return val

def prediction(num):
    entrees = [0]*7
    reseau = reseaux[num]
    typesInput = reseau[0]
    depI1 = reseau[1]
    depI2 = reseau[2]
    depN1 = reseau[3]
    depN2 = reseau[4]
    constantes = reseau[5]
    typesOutput = reseau[6]
    val1 = calculInput(num, typesInput)[0]
    val2 = calculInput(num, typesInput)[1]
    indice = 0
    for poid in depI1:
        entrees[indice+2]+=poid*val1
        indice+=1
    indice = 0
    for poid in depI2:
        entrees[indice+2]+=poid*val2
        indice+=1
    indice = 0
    for poid in depN1:
        entrees[indice+4]+=np.tanh(entrees[2]+constantes[0])*poid
        indice +=1
    indice = 0
    for poid in depN2:
        entrees[indice+4]+=np.tanh(entrees[3]+constantes[1])*poid
        indice +=1


    if max(entrees[4], entrees[5], entrees[6])>=0:
        if max(entrees[4], entrees[5], entrees[6]) == entrees[4]:
            afaire =typesOutput[0]
        elif max(entrees[4], entrees[5], entrees[6]) == entrees[5]:
            afaire = typesOutput[1]
        else:
            afaire = typesOutput[2]
    else:
        afaire = -1

    if afaire == 0:
        mouvRnd(num)
    elif afaire == 1:
        mouvGauche(num)
    elif afaire == 2:
        mouvDroite(num)
    elif afaire == 3:
        mouvBas(num)
    elif afaire == 4:
        mouvHaut(num)





def critereSelection(x, y):

    for gen in range(nbEtappes):
        for numEntite in range(nbEntites):

            x[numEntite] = (x[numEntite]+ mouvX[gen][numEntite])
            y[numEntite] = (y[numEntite] + mouvY[gen][numEntite])

    survivants = [0]*nbEntites
    for i in range(nbEntites):
        if x[i]>=nbColones*3/4 and y[i]>=nbLignes*3/4 :
            survivants[i]=1
    return [survivants, x, y]

def mutation(sansmutation):
    reseau2 = sansmutation.copy()
    achanger = random.randint(1, 5)
    if achanger != 5:
        p = [1, -1]
        indice = random.randint(0, 1)
        nvPoid = (reseau2[achanger][indice] + reseau2[achanger][indice]/35*p[random.randint(0, 1)] )%9
        if nvPoid>4:
            nvPoid= -4+nvPoid%4
        if indice == 0:
            reseau2[achanger] = [nvPoid, reseau2[achanger][1]]
        else:
            reseau2[achanger] = [reseau2[achanger][0], nvPoid]
        return reseau2
    else:
        p = [1, -1]
        indice = random.randint(0, 4)
        try:
            nvPoid = (reseau2[achanger][indice] + reseau2[achanger][indice] / 35 * p[random.randint(0, 1)]) % 3
        except:
            print(reseau2)
        if nvPoid > 1:
            nvPoid = -1 + nvPoid % 1
        if indice == 0:
            reseau2[achanger] = [nvPoid, reseau2[5][1], reseau2[5][2], reseau2[achanger][3], reseau2[achanger][4]]
        elif indice == 1:
            reseau2[achanger] = [reseau2[5][0], nvPoid, reseau2[5][2], reseau2[achanger][3], reseau2[achanger][4]]
        elif indice == 2:
            reseau2[achanger] = [reseau2[5][0],reseau2[5][1], nvPoid, reseau2[achanger][3], reseau2[achanger][4]]
        elif indice == 3:
            reseau2[achanger] = [reseau2[5][0],reseau2[5][1], reseau2[5][2], nvPoid, reseau2[achanger][4]]
        elif indice == 4:
            reseau2[achanger] = [reseau2[5][0],reseau2[5][1], reseau2[5][2], reseau2[achanger][3], nvPoid]

        return reseau2


def calculnbEnfants(nbSurvivants):
    nbEnfants = [0]*(nbEntites+nbSurvivants)
    for i in range(nbSurvivants-1):
        id = random.randint(0, nbEntites + nbSurvivants - 1)
        while nbEnfants[id]==1:
            id = random.randint(0, nbEntites + nbSurvivants - 1)
        nbEnfants[id]=1
    serie = 0
    res = []
    for i in range(len(nbEnfants)):
        if nbEnfants[i]==0:
            serie+=1
        else:
            res.append(serie)
            serie = 0
    res.append(serie)
    return res

nvx = xDepart[:]
nvy = yDepart[:]
nbSurvivants = []
nbGenerations =300

def predictiontest(num, reseaux):
    l = [reseaux[i][1][0] for i in range(nbEntites)]
    if l[num]>=0:

        mouvDroite(num)

    else:

        mouvGauche(num)
        print('G')




for gen in range(nbGenerations):
    print("gen", gen)
    x = nvx[:]
    y = nvy[:]
    mouvX = []
    mouvY = []

    for i in range(nbEtappes):
        mouvX.append([0] * nbEntites)
        mouvY.append([0] * nbEntites)
        for i in range(nbEntites):
            prediction(i)

    if gen == nbGenerations-1:
        afficher(x, y, mouvX, mouvY, 3)

        nvx = [nvx[i]+mouvX[-1][i] for i in range(nbEntites)]
        nvy = [nvy[i]+mouvY[-1][i] for i in range(nbEntites)]
        pos = [[nvy[i], nvx[i]] for i in range(nbEntites)]


    #afficher(x, y, mouvX, mouvY, 3)

    res = critereSelection(x, y)

    nvreseaux = []
    nvx= res[1]
    nvy = res[2]


    survivants = res[0]
    k = survivants.count(1)
    nbEnfants = calculnbEnfants(k)
    nbSurvivants.append(k)
    print(k)
    numero = 0
    indice =0
    for individu in survivants:
        if individu == 1:
            for i in range(nbEnfants[numero]):
                nvreseaux.append(mutation(reseaux[indice]))


            numero += 1
        indice += 1
    reseaux = copy.deepcopy(nvreseaux)

    pos = [[random.randint(0, nbLignes-1),random.randint(0, nbColones-1)] for i in range(nbEntites)]
    nvx = [pos[i][0] for i in range(nbEntites)]
    nvy =[pos[i][1] for i in range(nbEntites)]





x1 = [i for i in range(nbGenerations)]
print(nbSurvivants)
print(len(nbSurvivants))
plt.plot(x1, [nbSurvivants[i]/nbEntites for i in range (nbGenerations)], c = 'green')
plt.xlim([0, nbGenerations-1])
plt.ylim([0, 1])
plt.show()
print(reseaux)
print(pos)
afficher(x, y, mouvX, mouvY, 3)



