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 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 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).

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 valid DSA signature for the public key (q, p, g, y). There are multiple valid signatures, you may output any of them.