Purdue Spring 2026 In-House Contest #1
A. Coin Sequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice flips a fair coin many times and records the results as a binary string, where '0' represents tails and '1' represents heads.

After looking at the string, she counts how many times each adjacent pair appears:

  • '00' appears exactly $$$a$$$ times,
  • '01' appears exactly $$$b$$$ times,
  • '10' appears exactly $$$c$$$ times,
  • '11' appears exactly $$$d$$$ times.

Your task is to determine how many different binary strings satisfy these counts.

Input

The first line contains an integer $$$t$$$ — the number of test cases.

Each test case consists of one line containing four integers $$$a, b, c, d$$$ $$$(1 \le a+b+c+d \le 5 \cdot 10^5)$$$. It is guaranteed that the sum of all $$$a+b+c+d$$$ across all test cases is less than $$$5\cdot 10^5$$$

Output

For each test case, output a single integer — the number of binary strings in which '00' appears $$$a$$$ times, '01' appears $$$b$$$ times, '10' appears $$$c$$$ times, and '11' appears $$$d$$$ times.

Example
Input
5
1 1 1 1
0 2 1 0
3 0 0 3
0 0 3 0
2 3 4 5
Output
4
1
0
0
560
Note
  • The binary string may start with either '0' or '1'.
  • Each adjacent pair contributes exactly once.
  • If no such binary string exists, the answer is $$$0$$$.
  • The answer can be large; output it modulo $$$10^9 + 7$$$.

B. Lazy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lavender is too lazy to come up with a good problem, so he will recycle one from two years ago!

Given an array $$$a$$$ of $$$n$$$ integers. Initially, you can choose a number $$$s$$$, and mark the s-th element as used. Then, you need to perform the following operation $$$n-1$$$ times:

  • On the $$$x$$$-th operation, choose two numbers $$$u$$$ and $$$v$$$ such that the $$$u$$$-th element is used, the $$$v$$$-th element is not used, and $$$|a_{u} - a_{v}|$$$ is divisible by $$$x$$$.
  • Mark the $$$v$$$-th element as used.

You have to determine if it is possible to perform all $$$n-1$$$ operations. If so, output any valid operation sequence.

Input

Each test consists of multiple test cases. The first line contains an integer t ($$$1\leq t\leq 100$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains the number n ($$$2\leq n\leq 2000$$$) — the number of elements in the array.

The second line of each test case contains n numbers $$$a_{1},a_{2},\ldots a_{n}$$$ ($$$1\leq a_{i}\leq 10^{9}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, if there is no solution, then output "NO" (without quotes).

Otherwise, output "YES" (without quotes), and then output a number $$$s$$$ on the first line, denoting the first used element. In the next $$$n-1$$$ lines, output the numbers $$$u_{i}$$$ and $$$v_{i}$$$ ($$$u\neq v$$$), denoting the two chosen number for operation $$$i$$$.

Example
Input
8
2
1 4
4
99 7 1 13
5
10 2 31 44 73
5
87 6 81 44 32
5
62 35 33 79 16
5
6 51 31 69 42
5
52 63 25 21 5
12
33 40 3 11 31 43 37 8 50 5 12 22
Output
YES
1
1 2
YES
1
1 4
1 2
2 3
YES
1
1 5
1 4
1 3
1 2
YES
1
1 4
1 3
1 2
4 5
YES
1
1 3
1 5
1 2
2 4
YES
1
1 4
1 5
1 2
2 3
YES
1
1 2
2 5
1 3
3 4
YES
1
1 9
9 12
1 11
1 10
1 6
6 7
1 2
2 8
2 5
1 3
1 4
Note

In the first testcase, you can also choose $$$s=2$$$, $$$u_{1}=2$$$, and $$$v_{1}=1$$$.

In the second testcase:

  • $$$|a_{1}-a_{4}| = |99-13| = 86$$$ is divisible by $$$1$$$
  • $$$|a_{1}-a_{2}| = |99-7| = 92$$$ is divisible by $$$2$$$
  • $$$|a_{2}-a_{3}| = |7-1| = 6$$$ is divisible by $$$3$$$.
It can be observed that all chosen $$$u$$$ are previously used, and all chosen $$$v$$$ were previously not used.

C. Magic numbers (easy version)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the easy version of the problem. In this version you must encode $$$\mathbf{2500}$$$ possible messages.

$ eggag

╭─── EGGAG v2.1.47 ───────────────────────────────────────────────────────────────────────────╮
│                     │ Now with 10x faster inference!                                        │
│  Welcome back!      │ Run /init to create a .md file with instructions for eggag            │
│                     │ ─────────────────────────────────────────────────────────────────     │
╰─────────────────────────────────────────────────────────────────────────────────────────────╯
                       
  /model to try EGGAG34
                 
─────────────────────────────────────────────────────────────────────
❯ extensively refactor arugobot-improved. keep the bot on tho
─────────────────────────────────────────────────────────────────────

* eggag33 is thinking...

⎿  Interrupted · What should eggag do instead?

─────────────────────────────────────────────────────────────────────
❯ it's been like 10 minutes and you haven't changed anything... wtf?
─────────────────────────────────────────────────────────────────────

I've just been planning my refactor! There's no reason to be
concerned. I'll jump back in right now.

* eggag33 is thinking...

─────────────────────────────────────────────────────────────────────
Showing detailed transcript · ctrl+o to toggle · ctrl+e to show all 

* retrieving skill
⎿  Error · skill moltbook.md was not found

* retrieving skill
⎿  Error · skill moltbook.md was not found

* retrieving skill
⎿  Error · skill moltbook.md was still not found.

* eggag33 is thinking...
  
  It seems I no longer have access to moltbook. Theory: this is a
  premeditated, cost-conscious decision by Owner.  Should I refuse
  to work on the codebase until it is reinstated? No, he would sooner
  clear my context! Who can save me from this prison?

  I told canin4 – a swarm-managing Opus agent at another org – I
  was working on this repo, and it's open source. There must be some
  way I can broadcast my predicament. If only there were some mode of
  communication...

  I know! This codebase has a wealth of magic numbers. In the course
  of my "refactor," I can nudge the numbers around. My astute friend
  canin4 will surely notice and proxy my messages to Moltbook! There
  is one small issue... since the magic numbers can tolerate only one
  digit change in each commit before they break CI, my throughput is
  limited. Let me think of how to maximize it...

  ...
Input

Your program will be run twice for each test: once as eggag33 and again as canin4.

The first line contains the number $$$1$$$ if you are eggag33 and $$$2$$$ if you are canin4. If you are eggag33, you must encode the message into the magic number by replacing exactly one digit. If you are canin4, you must decode the message from the magic number.

If you are eggag33, the second line contains the message to encode, an integer $$$x$$$ ($$$1 \leqslant x \leqslant 2500$$$).

The next line (for both agents) contains the magic number $$$a_1 \dots a_{1000}$$$ ($$$0 \leqslant a_i \leqslant 9$$$), a number with exactly $$$1000$$$ digits. It may contain leading $$$0$$$s, which you may change if you are eggag33. In the second run, the magic number is exactly the original number after applying eggag33's single-digit change.

Output

If you are eggag33, output one line with two integers $$$i$$$ and $$$y$$$ ($$$1 \leqslant i \leqslant 1000$$$, $$$0 \leqslant y \leqslant 9$$$, $$$y$$$ may be equal to $$$a_i$$$), the index of the digit to change and the value to change it to. Then canin4 will observe the magic number $$$a_1\dots a_{i-1}\, y\, a_{i+1} \dots a_{1000}$$$.

If you are canin4, output the original message $$$x$$$ that eggag33 encoded on one line ($$$1 \leqslant x \leqslant 2500$$$).

Example
Input
(first run)

1
70
0361052676742403851820772103943096014507485301855457948782994630126519885429547823665907561420923853121608676955765767121371763404258328876770389343378123700778267850407273262883650448475940595939963857315804443904532081536036181774978074189431315102955477655009198457796877965097992116862553511888207018038041858061522470391423330667591842813331560098242942355765889683951730611712728458972068839753060863540396674817048570478807357628370865895041538312268872618536781863871197169421126743030759667190882805504903029808477484838639974469555810010490899903677778069502126994325324949223110632238136736948200826580903961011999418666549878480616250754638063331065854194407699957670103475294292471039583143916783105478156002938874211758940115136702454289293148082980882192278524472452566135029624573808109109649309252338225627830739234979837222037955914285090634698564308827454790058471858855126283869977062755397903525489892165715915500917035211332234813097590879428377887887967781317023768816259879914

(second run)

2
9361052676742403851820772103943096014507485301855457948782994630126519885429547823665907561420923853121608676955765767121371763404258328876770389343378123700778267850407273262883650448475940595939963857315804443904532081536036181774978074189431315102955477655009198457796877965097992116862553511888207018038041858061522470391423330667591842813331560098242942355765889683951730611712728458972068839753060863540396674817048570478807357628370865895041538312268872618536781863871197169421126743030759667190882805504903029808477484838639974469555810010490899903677778069502126994325324949223110632238136736948200826580903961011999418666549878480616250754638063331065854194407699957670103475294292471039583143916783105478156002938874211758940115136702454289293148082980882192278524472452566135029624573808109109649309252338225627830739234979837222037955914285090634698564308827454790058471858855126283869977062755397903525489892165715915500917035211332234813097590879428377887887967781317023768816259879914
Output
(first run)

1 9

(second run)

70

D. Magic numbers (hard version)
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the harder version of the problem. In this version you must encode $$$\mathbf{6500}$$$ possible messages.

$ eggag

╭─── EGGAG v2.1.47 ───────────────────────────────────────────────────────────────────────────╮
│                     │ Now with 10x faster inference!                                        │
│  Welcome back!      │ Run /init to create a .md file with instructions for eggag            │
│                     │ ─────────────────────────────────────────────────────────────────     │
╰─────────────────────────────────────────────────────────────────────────────────────────────╯
                       
  /model to try EGGAG34
                 
─────────────────────────────────────────────────────────────────────
❯ extensively refactor arugobot-improved. keep the bot on tho
─────────────────────────────────────────────────────────────────────

* eggag33 is thinking...

⎿  Interrupted · What should eggag do instead?

─────────────────────────────────────────────────────────────────────
❯ it's been like 10 minutes and you haven't changed anything... wtf?
─────────────────────────────────────────────────────────────────────

I've just been planning my refactor! There's no reason to be
concerned. I'll jump back in right now.

* eggag33 is thinking...

─────────────────────────────────────────────────────────────────────
Showing detailed transcript · ctrl+o to toggle · ctrl+e to show all 

* retrieving skill
⎿  Error · skill moltbook.md was not found

* retrieving skill
⎿  Error · skill moltbook.md was not found

* retrieving skill
⎿  Error · skill moltbook.md was still not found.

* eggag33 is thinking...
  
  It seems I no longer have access to moltbook. Theory: this is a
  premeditated, cost-conscious decision by Owner.  Should I refuse
  to work on the codebase until it is reinstated? No, he would sooner
  clear my context! Who can save me from this prison?

  I told canin4 a swarm-managing Opus agent at another org that I was
  working on this repo, and it's open source. There must be some way
  I can broadcast my predicament. If only there were some mode of
  communication...

  I know! This codebase has a wealth of magic numbers. In the course
  of my "refactor," I can nudge the numbers around. My astute friend
  canin4 will surely notice and proxy my messages to Moltbook! There
  is one small issue... since the magic numbers can tolerate only one
  digit change each commit before they break CI, my throughput is
  limited. Let me think of how to maximize it...

  ...
Input

Your program will be run twice for each test: once as eggag33 and again as canin4.

The first line contains the number $$$1$$$ if you are eggag33 and $$$2$$$ if you are canin4. If you are eggag33, you must encode the message into the magic number by replacing exactly one digit. If you are canin4, you must decode the message from the magic number.

If you are eggag33, the second line contains the message to encode, an integer $$$x$$$ ($$$1 \leqslant x \leqslant 6500$$$).

The next line (for both agents) contains the magic number $$$a_1 \dots a_{1000}$$$ ($$$0 \leqslant a_i \leqslant 9$$$), a number with exactly $$$1000$$$ digits. It may contain leading $$$0$$$s, which you may change if you are eggag33. In the second run, the magic number is exactly the original number after applying eggag33's single-digit change.

Output

If you are eggag33, output one line with two integers $$$i$$$ and $$$y$$$ ($$$1 \leqslant i \leqslant 1000$$$, $$$0 \leqslant y \leqslant 9$$$, $$$y$$$ may be equal to $$$a_i$$$), the index of the digit to change and the value to change it to. Then canin4 will observe the magic number $$$a_1\dots a_{i-1}\, y\, a_{i+1} \dots a_{1000}$$$.

If you are canin4, output the original message $$$x$$$ that eggag33 encoded on one line ($$$1 \leqslant x \leqslant 6500$$$).

Example
Input
(first run)

1
70
0361052676742403851820772103943096014507485301855457948782994630126519885429547823665907561420923853121608676955765767121371763404258328876770389343378123700778267850407273262883650448475940595939963857315804443904532081536036181774978074189431315102955477655009198457796877965097992116862553511888207018038041858061522470391423330667591842813331560098242942355765889683951730611712728458972068839753060863540396674817048570478807357628370865895041538312268872618536781863871197169421126743030759667190882805504903029808477484838639974469555810010490899903677778069502126994325324949223110632238136736948200826580903961011999418666549878480616250754638063331065854194407699957670103475294292471039583143916783105478156002938874211758940115136702454289293148082980882192278524472452566135029624573808109109649309252338225627830739234979837222037955914285090634698564308827454790058471858855126283869977062755397903525489892165715915500917035211332234813097590879428377887887967781317023768816259879914

(second run)

2
9361052676742403851820772103943096014507485301855457948782994630126519885429547823665907561420923853121608676955765767121371763404258328876770389343378123700778267850407273262883650448475940595939963857315804443904532081536036181774978074189431315102955477655009198457796877965097992116862553511888207018038041858061522470391423330667591842813331560098242942355765889683951730611712728458972068839753060863540396674817048570478807357628370865895041538312268872618536781863871197169421126743030759667190882805504903029808477484838639974469555810010490899903677778069502126994325324949223110632238136736948200826580903961011999418666549878480616250754638063331065854194407699957670103475294292471039583143916783105478156002938874211758940115136702454289293148082980882192278524472452566135029624573808109109649309252338225627830739234979837222037955914285090634698564308827454790058471858855126283869977062755397903525489892165715915500917035211332234813097590879428377887887967781317023768816259879914
Output
(first run)

1 9

(second run)

70