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.

• 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 approved cryptographic hash function H (for example SHA-2). The hash output must be an N-bit integer.
• Choose an N-bit prime q.
• 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 number 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).

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 only line 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.

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