Problem A
SHA-256

Write an implementation of SHA-256.

Input

Each line of the input consists of the hexadecimal encoding of an array of bytes that should be be hashed, i.e., you may assume that the length of each input is a multiple of 8 bits. Note that the empty string is a valid input and that also the last input line ends with a newline.

Output

For each input, output one line, containing the hexadecimal encoding of the hash value of the bytes encoded in the input. Note that it is the encoded bytes that must be hashed and not the ASCII characters in the hexadecimal encoding. Note also that the last line should end with a single newline.

e5
4719
93006a
889468b1

ab61ba11a38b007ff98baa3ab20e2a584e15269fd428db3c857e2a2d568b5725
60acb27227ef97fb8ad343bf910cf5f451d8af50498e4b7d293bbd97e6c50c9b
1dc0b9dd1a9633d9c967c18ca23a68457850bd5e67194d3fc977931d50f455ea
855b2244b875ed9ae089fb10d84c85257f30c65ea1325c2f76727a582ba4c801