The DSA (Digital Signature Algorithm) is a public-key cryptographic algorithm for creating digital signatures. The signature is created secretly but can be verified publicly. This means that only one subject can create a signature, but anyone can verify its correctness. The algorithm is based on the computational complexity of taking logarithms in finite fields.

The first phase of key generation is a choice of algorithm parameters which may be shared between different users of the system.

• Choose an approved cryptographic hash function H (for example SHA-2). The hash output may be truncated to the size of a key pair.
• Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The minimal recommended values for L and N are 1024 and 160.
• Choose an N-bit prime q. N must be less than or equal to the hash output length.
• Choose an L-bit prime modulus p such that p − 1 is a multiple of q.
• Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h ^{(p − 1) / q} mod p for some arbitrary h (1 < h < p − 1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h = 2 is used.

Given a set of parameters, the second phase computes private and public keys for a single user:

• Choose x by some random method, where 0 < x < q.
• Calculate y = g ^x mod p.
• Public key is (p, q, g, y). Private key is x.

Let m be the message and H(m) the hash value of that message.

• Generate a random per-message value k where 0 < k < q.
• Calculate r = (g^k mod p) mod q.
• In the unlikely case that r = 0, start again with a different random k.
• Calculate s = k⁻¹(H(m) + x r) mod q.
• In the unlikely case that s = 0, start again with a different random k.
• The signature is (r, s).

• Reject the signature if 0 < r < q or 0 < s < q is not satisfied.
• Calculate w = s⁻¹ mod q.
• Calculate u₁ = H(m) w mod q.
• Calculate u₂ = r w mod q.
• Calculate v = ((g^u₁ y^u₂) mod p) mod q.
• The signature is valid if v = r.

Given the public key (q, p, g, y) and the hash value of the message H(m) you are to create a valid signature (r, s).

The single line of input contains integers N, L, q, p, g, y, H(m). The following limitations are applied:

• 3 ≤ N ≤ 36;
• 6 ≤ L ≤ 60, L ≥ N + 3;
• q is an exactly N-bit integer;
• p is an exactly L-bit integer;
• 1 < g < p;
• 0 ≤ y < p;
• H(m) is an N-bit integer.

The public key is guaranteed to be generated as described above.

The single line of output should contain the integers r and s separated with space. The pair (r, s) must be valid DSA signature for the public key (q, p, g, y). There are multiple valid signatures, you may output any of them.