Merkle Tree Root Hash

This problem requires you to build a balanced Merkle tree from a list of data blocks using the SHA-256 hash function. At the leaf level, each data block is hashed using SHA-256. If the number of data blocks is not a power of two, you must pad the list with the string ExtraNode until it reaches the next power of two. Then, in each upper level, you pair adjacent hash values, concatenate them, and compute the SHA-256 hash of the result. This process is repeated until a single hash (the root) remains.

Note: All hash computations should be done using the standard SHA-256 algorithm. All formulas, if any, must be represented using LaTeX format. For example, if you need to show the computation of hash from two concatenated strings A and B, you can provide it in LaTeX as:

\( h_{i} = SHA256(A+B) \)

Your solution must read input from standard input (stdin) and write output to standard output (stdout).

inputFormat

The first line of input contains an integer \(n\), the number of data blocks. Each of the following \(n\) lines contains a non-empty string that represents a data block.

Example:

4
block1
block2
block3
block4

outputFormat

Output a single line containing the Merkle tree root hash computed with the SHA-256 algorithm.

1
data1

6b277e6f640c8d11d2a11b3438ec9c37e6f3d5580154a9b251d24f5bba33ebc6