Generate a Monotonic Function Overview

In this challenge, your task is to randomly generate a monotonic mathematical function between two sets.

Input

Your inputs are two positive integers s and n.

After getting these inputs, your program shall generate a random mathematical function f from the set {0,1,...,s-1}n to {0,1,...,s-1}.
In other words, f is a "rule" that takes in an n-tuple of integers between 0 and s-1, and returns one such integer.
Additionally, f should be monotonic in the following sense.
If A and B are two n-tuples such that A[i] &ge; B[i] holds for every coordinate i, then f(A) &ge; f(B).

The exact distribution of the monotonic functions f doesn't matter, as long as each such function has a positive probability of being generated (assuming a perfect RNG).

Output

Your output shall be an enumeration of the inputs and outputs of f.
It shall contain all n-tuples of integers between 0 and s-1 in some order, each one being followed by the corresponding output of f.
The exact output format is flexible (within reason).

Examples

The inputs s = 3 and n = 2 might produce the output

(0, 0) 0
(0, 1) 1
(0, 2) 2
(1, 0) 0
(1, 1) 1
(1, 2) 2
(2, 0) 1
(2, 1) 1
(2, 2) 2


It contains all the pairs over the set {0, 1, 2} exactly once, and each one is followed by its f-value.
The monotonicity condition is also satisfied.
The tuples are given here in lexicographical order, but this is not necessary.

As another example, s = 2 and n = 4 might produce

(0, 0, 0, 0) 0
(0, 0, 0, 1) 0
(0, 0, 1, 0) 0
(0, 0, 1, 1) 0
(0, 1, 0, 0) 1
(0, 1, 0, 1) 1
(0, 1, 1, 0) 1
(0, 1, 1, 1) 1
(1, 0, 0, 0) 0
(1, 0, 0, 1) 1
(1, 0, 1, 0) 0
(1, 0, 1, 1) 1
(1, 1, 0, 0) 1
(1, 1, 0, 1) 1
(1, 1, 1, 0) 1
(1, 1, 1, 1) 1


The following are all possible outputs for s = 2 and n = 2 (up to reordering the tuples); your program should randomly output one of them:

(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 0
-------
(0,0) 0
(0,1) 0
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 0
(1,0) 1
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 0
(1,1) 1
-------
(0,0) 0
(0,1) 1
(1,0) 1
(1,1) 1
-------
(0,0) 1
(0,1) 1
(1,0) 1
(1,1) 1


Rules and Scoring

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.
Code with explanation is preferred.

There are no restrictions on time complexity, but I'll give a bonus of -15 % if your solution is always guaranteed to finish in a certain amount of time (depending on the inputs, and assuming a perfect RNG that runs in constant time).
Pyth, 35 bytes (38 - 15% = 31.45 farther down)

#I!sm&gt;&lt;FhMds&lt;MCeMd^JC,mOQK^UQvzK2JB


Demonstration

Input is in the format:

n
s


Output is in the format:

[[value, tuple], [value, tuple], ...]


Simply generates random possibilities and tests them.



Alternative 37 byte version which I believe qualifies for the bonus:

Of!sm&gt;&lt;FhMds&lt;MCeMd^T2mC,d^UQvz^UQ^Qvz


Demonstration

This starts by generating all possible monotonic functions, then outputs one at random. It is much slower, and tops out at 2,2.