In this problem, you can again assume that all inputs, and all integers you will work with,

fit in a machine word; costs should be given by counting word operations.

We want to pave a chessboard of size n$\backslash$times n$,$ with n a power of $2,$ with tiles of the following

shape:

type $1$ type $2$ type $3$ type $4$

$2$

Of course, this is not possible $($do you see why?$).$ But now, say we remove one square from

the board, at position i$,$ j$.$ It turns out that paving becomes possible.

$1.$ Give a divide$-$and$-$conquer algorithm that takes n$,$ i$,$ j as input and returns a list of

position of tiles of the form $[($ui

$,$ vi

$,$ ti$)]$i$<=$N $,$ with integers ui

$,$ vi that specify the top$-$left

coordinate of the $2\backslash$times $2$ area where we put tile i$,$ and ti in $\{1,...,4\}$ its type. Analyse

the runtime.