A higher resolution is required to access the IDE

- 29

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

Implement a slightly modified version of the SHA-256 hash.A full description of the SHA-256 algorithm can be found on Wikipedia: https://en.wikipedia.org/wiki/SHA-2#Pseudocode

A detailed walkthrough can be found here: https://qvault.io/cryptography/how-sha-2-works-step-by-step-sha-256/

The only difference between the

**standard implementation**(detailed in the 2 links above) and our implementation is in the definition of the

**initial hash values**(referred to as h0 - h7 in the links above).

The

**standard implementation**uses the first 32 bits of the fractional parts of the square roots of the

**first**8 primes (2, 3, 5, 7, 11, 13, 17, 19). We will instead use the first 32 bits of the fractional parts of the square roots of the

**next**8 primes (23, 29, 31, 37, 41, 43, 47, 53), given here in hexadecimal form:

0xcbbb9d5d

0x629a292a

0x9159015a

0x152fecd8

0x67332667

0x8eb44a87

0xdb0c2e0d

0x47b5481d

The reason we're using different initial hash values is so that you can't use built-in hash functions, e.g. python's hashlib.sha256.

Apart from this change in initial hash values, the algorithm proceeds

**exactly the same as the standard implementation**. Note: the "round constants" are not changed, i.e. they are the same as in the standard implementation.

You will be given a string, you must convert that string to a sequence of bits (using ASCII) and hash it using our version of the SHA-256 algorithm.

Input

**One line:**a string

`S`to hash.

Output

**One line:**the 64-character hash value

`H`output by our version of the SHA-256 algorithm in lowercase hexadecimal form.

Constraints

All characters of the string will be printable ASCII characters in the range [32 - 126] inclusive.

Example

Input

Ravenclaw

Output

70ac5b0feb57d7b1823a905a398863318594dd996d5c40ecced5089935e7a922

A higher resolution is required to access the IDE