Last Updated: 2017-09-11 Mon 14:08

CSCI 1103: Java Install; Edit, Compile, Run, Test, Repeat

CODE DISTRIBUTION: lab01-code.zip

CHANGELOG:

Mon Sep 11 14:07:39 CDT 2017
The HelloLab.java program was listed incorrectly and needed a comma in it. The correct output string is 
Hello, Lab!

and now reads correctly.

Table of Contents

1 Rationale

Completing this lab will ensure that you know how to edit, compile, and run a Java program, check the correctness of your programs using provided test cases, and submit your work to Canvas. All programming work will involve these steps, so this lab is a chance to get oriented with the assistance of course staff.

This lab will also introduce you to some basic command line operations such as changing between folders and compiling on the command line.

Associated Reading

Eck Chapter 2
Chapter 2 discusses simple Java programs, printing, compilation, and running programs.
Video Walk-through
A walk-through of DrJava installation, use, and completion of some Lab 1 code is hosted on YouTube here: https://www.youtube.com/watch?v=n0FbRPrMoU0

This video is based on a previously taught class (CS 211 at GMU) but much of what is covered applies for us.

2 Programming Environment

2.1 Lab Computers

Lab computers come with Java installed and DrJava readily available via a menu selection. Your lab leader will demonstrate this towards the beginning of lab.

2.2 Personal Environment

You may choose whatever environment you like to construct your programs but the only officially supported development tools for the course are DrJava and the command line javac and java programs.

If you will use DrJava on your own computer, get the most updated, GMU edition which is downloadable here:

https://cs.gmu.edu/~kauffman/drjava/

You will also need to download the Java Standard Development Kit (JDK) which has the compiler and associated programs. It is available here:

http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html

3 Download Lab Code and Setup

Most labs come with some code that you need to use, which is linked at the top of the lab specification.

  1. Download the zip file lab01-code.zip
  2. Unzip the archive, which will create a folder named lab01-code. Your course staff will show you how to unzip things this both graphically and via the command line.
  3. The folder already contains some code such as test cases and the junit-1103.jar file which you will use. In particular, you will need this junit-1103.jar file for every single testing file we use over the semester, so keep it handy. You can copy it from assignment to assignment as needed.
  4. Create your programs in this directory: lab01-code for this lab.
  5. During submission, you will create a zip archive for your programs and submit the zip to Canvas.
File State Notes
PARTNERS.txt Edit Fill in your name and the name of your partner in this text file
Lab01Tests.java Testing For testing your code, don't edit it but feel free to look
junit-1103.jar Testing For testing, don't try to edit this one
HelloLab.java Create Create this file for Problem 1
CSWisdom.java Create Create this file for Problem 2

4 Problem 1: Hello, Lab! (TESTED)

4.1 Create a Java File, Compile and Run

Create a new file called HelloLab.java in your lab directory. Do this with DrJava by copying the below program into a new file and then saving it. The name will likely default to HelloLab.java 

public class HelloLab {
  public static void main (String[] args) {
    System.out.println("Hello, Lab!");
  }
}

Compile and Run this program in DrJava by pressing appropriate buttons. Examine the results of the run.

4.2 Compile and Run on the Command Line

In a new terminal, compiling and running the program will typically look like the following. 

lila [~]% cd lab01-code                            # change to the lab01-code folder

lila [lab01-code]% ls                              # show files in this folder
HelloLab.java  junit-1103.jar  Lab01Tests.java	PARTNERS.txt

lila [lab01-code]% javac HelloLab.java             # compile the java code in HelloLab

lila [lab01-code]% ls                              # show files, HelloLab.class exists
HelloLab.class	HelloLab.java  junit-1103.jar  Lab01Tests.java	PARTNERS.txt

lila [lab01-code]% java HelloLab                   # run the HelloLab program
Hello, Lab!

Many of the demonstrations of how programs run will be shown on the command line as above. Note that my machine is called lila and I am in a directory (folder) called lab01-code. Commands start after the % on the above lines such as javac HelloLab.java. Your command line environment will look different from this and require you to learn a little in order to navigate and run programs.

4.3 GUI vs Command Line

GUI tools often involve pressing buttons to accomplish compile/run. Regardless of your programming environment or platform, all 1103 students must know how to compile and run java programs on the command line. Course staff may require that you demonstrate problematic programs on the command line in order to diagnose and if you cannot do so you may not get the help you want. If your GUI tool should fail you, the command line provides a reliable and predictable alternative that, though initially intimidating to use, ultimately provides maximum power and flexibility.

5 Problem 2: CS Wisdom (TESTED)

Use HelloLab.java as a template and create the file CSWisdom.java which prints the following message. Make sure to adhere exactly to the formatting below or your program will fail the test cases. 

If in physics there's something you don't understand, you can always
hide behind the uncharted depths of nature. You can always blame
God. You didn't make it so complex yourself. But if your program
doesn't work, there is no one to hide behind. You cannot hide behind
an obstinate nature. If it doesn't work, you've messed up.

- Edsger Dijkstra

Compile and run your code which should look something like this: 

lila [lab01-code]% javac CSWisdom.java
lila [lab01-code]% java CSWisdom
If in physics there's something you don't understand, you can always
hide behind the uncharted depths of nature. You can always blame
God. You didn't make it so complex yourself. But if your program
doesn't work, there is no one to hide behind. You cannot hide behind
an obstinate nature. If it doesn't work, you've messed up.

- Edsger Dijkstra
lila [lab01-code]%

Make sure to use System.out.println() to print each line separately so that you receive the proper output and pass the tests.

A common mistake is to try use only one System.out.println() but it is much easier to use many prints to get the output to look right.

6 Testing Locally Using JUnit

We will use the JUnit testing framework for testing in this course. It is a general example of a unit testing framework that comes in the form of a java archive which typically is a file with the .jar extension. JUnit is in the file junit-1103.jar and contains a variety of test-related classes. The specific tests for this lab are in Lab01Tests.java. At this point you do not need to understand this file but by the end of the semester test files will become dear to your heart.

6.1 Testing with DrJava

DrJava can run these tests by opening Lab01Tests.java and clicking on the Test button. Click on test errors to jump to the test code. Most of the time this will give identical results to the command line invocation though unusual circumstances sometimes cause a divergence of these two. DrJava already has junit-1103.jar baked into it so does not need to do anything special with that file.

6.2 Mac/Unix Users

To test your code use the following commands in a terminal. 

lila [lab01-code]% javac -cp  junit-1103.jar:.  *.java
lila [lab01-code]% java  -cp  junit-1103.jar:.  Lab01Tests
JUnit version 4.11
..
Time: 0.021

OK (2 tests)

The OK indicates that all tests have passed.

6.3 Windows Users

To test your code use the following commands. 

lila [lab01-code]% javac -cp .;junit-1103.jar *.java
lila [lab01-code]% java  -cp .;junit-1103.jar Lab01Tests
JUnit version 4.11
..
Time: 0.021

OK (2 tests)

Note that in the Windows commands, there is a SEMICOLON ; rather than a colon : used in -cp .;junit-1103.jar.

6.4 Failed Tests

Should tests fail you may see something like this: 

lila [lab01-code]% javac -cp junit-1103.jar:. *.java
lila [lab01-code]% java -cp junit-1103.jar:. Lab01Tests
JUnit version 4.11
..E
Time: 0.006
There was 1 failure:
1) Lab00_2main(Lab01Tests)
org.junit.ComparisonFailure: expected:<...ou can always blame
[God. You didn't make it so complex yourself. But if your program
]doesn't work, there ...> but was:<...ou can always blame
[]doesn't work, there ...>
	at org.junit.Assert.assertEquals(Assert.java:115)
	at org.junit.Assert.assertEquals(Assert.java:144)
	at Lab01Tests.Lab00_2main(Lab01Tests.java:62)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:606)
	at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
	at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
	at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
	at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
	at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
	at org.junit.internal.runners.statements.RunAfters.evaluate(RunAfters.java:27)
	at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:271)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:70)
	at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:50)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:238)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:63)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:236)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:53)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:229)
	at org.junit.internal.runners.statements.RunBefores.evaluate(RunBefores.java:26)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:309)
	at org.junit.runners.Suite.runChild(Suite.java:127)
	at org.junit.runners.Suite.runChild(Suite.java:26)
	at org.junit.runners.ParentRunner$3.run(ParentRunner.java:238)
	at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:63)
	at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:236)
	at org.junit.runners.ParentRunner.access$000(ParentRunner.java:53)
	at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:229)
	at org.junit.runners.ParentRunner.run(ParentRunner.java:309)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:160)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:138)
	at org.junit.runner.JUnitCore.run(JUnitCore.java:117)
	at org.junit.runner.JUnitCore.runMain(JUnitCore.java:96)
	at org.junit.runner.JUnitCore.runMainAndExit(JUnitCore.java:47)
	at org.junit.runner.JUnitCore.main(JUnitCore.java:40)
	at Lab01Tests.main(Lab01Tests.java:69)

FAILURES!!!
Tests run: 2,  Failures: 1

Of the 3 tests, 2 passed and 1 failed. Some failure information is given along with a stack trace for the failed test.

7 Getting Credit for this Lab

7.1 Partners for Labs

Students may elect to work with one partner on the labs or alone. If working with a partner, both partners must submit code and be physically present to have labs checked off by TAs, either in labs or outside of labs.

Make sure to fill in the text file PARTNERS.txt with information about who you worked with. It is included in the lab code and here is a sample of a completed form. 

These 1 or 2 people worked on this lab together and will share a grade
for it.

PARTNER 1
Name: Turanga Leela
NetID: leel0897@umn.edu

PARTNER 2
Name: Philip Fry
NetID: fryph135@umn.edu

Here is a sample of PARTNERS.txt for a student who worked on their own. 

These 1 or 2 people worked on this lab together and will share a grade
for it.

PARTNER 1
Name: Bender B. Rodriguez
NetID: brogri436@umn.edu

PARTNER 2
Name: 
NetID:

7.2 Demonstrate your code to Lab Staff (40%)

You should feel free at any time to get help from lab staff as you get stuck on the exercises.

By the end of the lab, make sure to demonstrate your code to a staff member. This will ensure that you receive full credit on the lab. Staff might ask you to

  • Change what is printed
  • Compile and run on the command line
  • Run tests in DrJava or on the command line
  • Show how to zip the folder with your programs in it

Be ready to do any or all of these.

7.3 Zip and Submit (60%)

Ensure that file PARTNERS.txt has your name and the name of your partner in it. This fill is located with the other Java files for the lab and can be edited with DrJava.

Once your are confident your code is working, you are ready to submit. Your lab folder should now have the following files in it. 

lila [lab01-code]% ls -1
CSWisdom.java
HelloLab.java
junit-1103.jar
Lab01Tests.java
PARTNERS.txt

Create a zip archive of your lab folder and submit it to blackboard. Submit only ZIP archives: not RAR, 7zip, GZ, TAR, or your favorite weird compressed format. Graders have LOTS of students to grade each and dealing with a single file format makes them less cranky and less likely to give 0 credit for things they cannot decompress.

If you do not know how to create a ZIP archive, read the following short tutorial.

On Canvas:

  • Click on the Assignments section
  • Click on the appropriate link for this lab
  • Scroll down to "Attach a File"
  • Click "Browse My Computer"
  • Select you Zip file and press OK

You can resubmit to blackboard as many times as you like up to the deadline. Also, you can revisit your submission(s), verify what file was uploaded by downloading it, and seeing what is there. It's up to you to upload the correct file!

Happy hacking!

8 Extras: Bender and ASCII Art Generators

Do not underestimate the entertainment power of ASCII art. A Google image search for ascii art yields an array of amusements. You might attempt to create a file called Bender.java which prints the following picture when its main() method is run. 

                      .-.
                     (   )
                      '-'
                      J L
                      | |
                     J   L
                     |   |
                    J     L
                  .-'.___.'-.
                 /___________\
            _.-""'           `bmw._
          .'                       `.
        J                            `.
       F                               L
      J                                 J
     J                                  `
     |                                   L
     |                                   |
     |                                   |
     |                                   J
     |                                    L
     |                                    |
     |             ,.___          ___....--._
     |           ,'     `""""""""'           `-._
     |          J           _____________________`-.
     |         F         .-'   `-88888-'    `Y8888b.`.
     |         |       .'         `P'         `88888b \
     |         |      J       #     L      #    q8888b L
     |         |      |             |           )8888D )
     |         J      \             J           d8888P P
     |          L      `.         .b.         ,88888P /
     |           `.      `-.___,o88888o.___,o88888P'.'
     |             `-.__________________________..-'
     |                                    |
     |         .-----.........____________J
     |       .' |       |      |       |
     |      J---|-----..|...___|_______|
     |      |   |       |      |       |
     |      Y---|-----..|...___|_______|
     |       `. |       |      |       |
     |         `'-------:....__|______.J
     |                                  |
      L___                              |
          """----...______________....--'

Source: Benjamin Weiland

While this involves some tedium, it will teach you several valuable lessons.

  • How to edit Java files reasonably quickly, perhaps discovering how to insert the same text in multiple lines at once to preface each line with System.out.println or that your editor of choice cannot perform such useful features.
  • Printing some characters such as double quotes (") and backslash (\) requires character escapes: preceding the character with a backslash as in 
    System.out.println("This was an \"easy lab\" \\ it will get more interesting");

A very interesting program would be one which takes a picture in a format such as PNG, JPG, or GIF and converts it to ASCII art. It's not hard to find such programs online but what's more interesting is how they work. Perhaps by the end of your CS career you will be writing such programs.

chris.jpg 

....,....,.....,,.,,,,,,,,,,...'......,::::,,,,,,,,,,,,,,,,........................,:''+#############################
,.,.,,.,..,,,,.,,,,,,,,,,,,,,.,',......,,:::,,,,,,,,,,,,,,..........................:;'+++#####++++++'+'+############
,,,.,.,,,,,,,.,,,,,,,,,,,,,,,,,',,.......,,:::,,,.....,,,,.,,,......................,:;''++++++';;::,,::;;'''+#++++##
,,,,,,,,,,,,,,,..,,,,,,,,,,,,,:',,,,,.....,,,:::,,.,...,,....,,,.....................::;;;;;;:::,,,,,,,,,:::::;;;;'''
,,,,.,,,.,,,,,,,,,.,,,,,,,,,,,:',,,,,.,.....,,:,::,,,,...,...........................,,::::::::,,,,,,,,,,,:::::::::;;
,,,,,,,,,,,,,,,,,,,,,,,,,,,...;;.,,,,.,.......,,:,:,.................................,,,,::::,,,,,,,,,,,,,::::;:,::;:
,,,,,,,,,,,,,,.,,,............;:.....,,.........,,,,,,,...............................,,,,:,,,,,.,,,,,,,,,::::::,::,:
,,,,,,,,,,,,,.................',..................,,,,,,,..............,.........,....,,:,,,,,.,,,,,,,,,,::::::::::,:
,,,,,,,,,,,...................'.....................,,,,:,,,,......,..,.,,,,,,,.......,,,,,,,,,,,,,,,,,:,,,:::,::,:,,
,,,,,.,,,.....................+............,..........,::,,:,,......,...,,,,,..,.......,,,,,,,,,,,,,,,,:,:,::::,,,,,,
,,,,,...,,....................'.............,.,,......,,;::,,,,,,,,,,,.,.,,,,..,.......,,,,,,,,,,,,:,,,,,,,:,,,,,,,,,
,,,,,,........................'.............;::.`..,,,,,,;::,:,..,,,,,..,,,:,,,........,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,.,,,,,,......................'.............:::,,,,,,,,.,,,,,,:::,,,,,:,;:::,::,.......,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,..,,,,.,.....,..............,'...........,.;:,:;,:';,:,;:',::::::::;:,,,,::;;:.,,.....,,,,,,,,,,,,,,,,,,,,.,,,,,,,,,
.,...,,,,..,,,,,.............:;.......,..,,,:;:;;;;'';;';;;::::::,,;;;:::;',;:,,.,.....,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,.,,...,,,.,,,,,,,...........;:.........,,:::;';::::+';;;;,,,;:,:.,.:;::',:;::;;;.......,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,...,..,,,,,,,,,,,,,.,,......':..,.,,.,,,:,';:;::;''+''',:;+;:,:,';:';;:;;:;;,,'':,.....,,,,,,,,,::,,,:,,,,,,,,,,,,,,
.....,,,,,,,,,,,,,,,,,,,,,,,,',,,,,,,,,,,::';;;;;;:'#;;::'''',;;;''':;;:::;,:';++',.....,,,,,,,,,,,,,:,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,',,,,,,,,:,,:;'.::;'';;';+'+:'::;+:';++.;;;:':':,+.;+',,,,,.,::,,:,,,,,,,,,,:,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,:':,,,,:,:,:';,;;:;''';;++#';:,;''+##+''.';'''+;++';+;':,;;:,,,:::,,,,,,,,,,,,:,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,:;:,,,,,,::'';:';;;+;;;++''::',''+#+++;:'';;+:'#'++++'+';,',:,::::,,:,:,,::,,::,:,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,:;;,,.:,::;;:;;;,::;;;'''++'::'';+'+;;;:,,:,..:;';;+++'+',:;,,,,::,,,,,:,,,,,:,,:,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,:';,.,:;::;;;:;;,:.,:,;+';;:;::;''',,,,,:;;'::,:;':;+#++'',,;;,,:::,,,::,::,:::,:,,,,,,,,,
,,,,,,,,,,,,,,.,,,,,,,,,,,,;;;..:;;'::::'',,:;;.:,;;;''::''+';:....:,,+:;:;:;;;''+++;,;::,,:,:,,:,:,:::::::,,,,,,,,,,
,,,,,,,,,,,,,..,,,,,.,,,,:,;;',;::'+;;.,;.;',,';.`,,,::,;;+;;:,:.,.,,;'''';;:;,:.#'+::',;,,:,,::,::,,:,,:::::,,,,,,::
,,,,,,,,,,,,,,,.,,.,,,,,.,:;';,:;;,;'';:';':;,,,::..:;;''';;::..:;:.,:'+'+''':;:;,++''''::,,:,::::::::,::,:,,,,,,,,:,
,,,,,,,,,,,,,,,,......,,,,,'':;:';::::;:,:;::;,:::;,,,:'+;;,::;,,:;;:;;+''++''++,:#+''++';,,,,::::,,:::::::,:,,,:::::
,,,,,,,,,,,,,,,,......,,,,:'',:'':,:;,,:,:,,:.,.,..:;''+;:,,.,,.:;;+;;:''+++++++;:+'#';++',,,,::::::,:,:::,:,,,,:::::
,,,......,,..........,,,,,,;::;;;';,;,:,.,,,';:;;:;;'++',.:...:;;';++:;;+;;++'+#;+##:#;.#':,,:,::::,::,:::::::,::::::
,,,...................,,,,:,:;:';;;;:;:;';::;;.;::''+::,:..`,.;''+'+++;'++;++++'+++#+'++,#;,,,:::::::::,,::::::::::::
..,,,..................:,.:,;;;':;;;,,;:;::,..,.;;'+;;'::::+,:'+#++';++;;+:+++#+''#++#+'++':,:::::;::::,:::::::::::::
,..,,,...............,:'::,;::+;::,.,,,,,,.....,,:::';'':+;;:'';++#+++#''+;+++##++###+#+''+:,::::::::::::::::::::::::
,,,,,,,..........,,...,';:::;,;;:.;:,':;';;;.;:,;'';;+'++'++:;''##+#'+#++#'##+##+#+######:':,,:::::::::::::::::::::;;
..,,,,,,...,,.,...:.,,:'::;:'::::':;:,.,,:'''+;:;'+++++++:+#++:##++##+#++#+#######+######++',,:::::::::::::::::::;;;;
,,,.,,,,,,,,::,,,.::;;',;;;';;;',:;:;:.`:`,+;;,;;'++'+#+##+#+;+#+#####+####+##############++,:,:::::::::::::::::;;;:;
,,,,,,,,,,,,,:;.:.';';;';'':,::':,::,,,,.`,`,:`.'';''++####+#+#############+###############+:,:::::::::::::::;:::::::
,,,,,,,,,,,,,,;;::+'+';'::::+:;++;:;;:',',..,.:;:++''+##+#######+++#########@##############+;::::;:::::::::;;:::::;:;
,,,,,,,,,,,,,,,:;;+++'';''#,+;;,,;,,,,:',;:;::;'''+#+'++##'############@@##@##@######@@#####',,:::::::::::;:;::::;;::
,,,,,,,,.,,..,,,,;+:;:+++':;:::;;,+,,,',;;';;''+'++++####+########@@#@########@#####@#@@###+':,,::;;:::::;:::::::::::
,,,,,,,,,,,,,,.,,:';';+'';:;;::.,:,:,:;,:'+'+''+++++##########+##@@@@@@@###@##@@#####@@@#@###:,::::;:::::;::::::;;::;
.,,,,,,,,,,,,,,::;,;'+'+,;'+''';;:'';;:::;'+++++##+###############@@@#@@##@########@###@@@###',::::::::::::;:::::::::
,,,,,,,,,,,,,,::;;;++++';:'''::;.';:;''';+++++######################@##@@@@###@#@##@@#@@@@@##+,:::::;:::;::::::;;::;;
,,,,,,,,,,,,,,:;''''+++';':;;::;::';::+++;+#+###########@#####@@@########@@#@@@#@####@@#@@@##+::,,:;;;;::;:::;:::::::
,,,,,,,,,,,,,,;;''+++++;:;+'''':,::;;;;+'+#+;+###########@##@@@###@@@####@##@##@@##@##@@##@@@+;:,,::;;::;;:::::::::::
,,,,,,,,,,,,,,'::''''+;'::;:'',,;;'';;;;;:'#+'#@@@@#######@@@@@@#@@@@@@######@#@@@#@##@@@##@##':,,::;;;:;;;;;::::::::
,,,,,,,,,,,:,:+''+;'':#+#'':';,:'';';'+++++#++###@@@@@#@#@@@@#@@#@###@######@@@#@@###@@@@@##@#+:,::::;;;;;;;:::::::::
,,,,,,,,,,,,,'+';'++++#:#'';,;';:;'''+++++##'#####@@@@@@@@@@#@###@@@#########@@@@@@@@@@@#@@@##+::,:::;:;:;;;:;;::;:::
:,,,,,,,,,,,,''+++++';:',';'+'#'+++++'''+#'########@@@@@@@@@@######@###########@#@@######@@@###+:,::::;;;;;;:::::::::
;::,,,,,,,,,,''++'++;::'+,;'#++#+####+''+##########@@@@@@@@@####################@@@@#@#@@#@@###+:,,:::;;;';:;;:;:::::
+##'::,,,,,::;';;'+',,:::++'+#######################@@@@@@@@####################@@@@@@##@##@@@#+:,,::;:;;;;;:;;;:;:::
######';:,,;'';;':,;;:;':'+''++#######@@#############@@@@@#######################@@@@@##@#@##@##',:::::;;;;;;:;;:::::
++#++####++;';;;:,;'';;'''+#+++#######################@@@#########################@@@@@@#########::,:::;;;;;;;;;;::::
::'++++####';,:;;:''';++'++##+#########################@@#########################@@@@@@###@@@##+;::::::;;;;;;:;:;:::
::::::'+#+';:;;:++;+';++'+++######################################################@@@@#@@##@##@#@+:::::::;;;;;:;;::::
:::,:,,:::'',;:';+#+#'+'+++##########'+############################################@@@@@@@#@#@###+:::,::::;;;;';;;;:;
::::,::,,,:,,;'+++##@#+++'+++#############################################+#########@@@@@@@@@@#@#+;:::::::;;;;';;;;;;
:::::::::,;,:;'+######+'+#++++############################################+#++#######@@@@@##@#@@##':::::::;:;;;;;;;;;
::::::::,:':;:'######+'''+++++#######################################+++++++++########@@@@@@@#@@##+;::::,:::;;;;'';;;
::::::::::::,;++##@@#+''''++++++####################################+++++++++++########@@@@@@#@@@##':::::::;;;;;''';;
::::::::::;;;;+######+'''''+++++++################################++++++++++++++++######@#@#@#@@@###;::::::::;;';''''
::::::::::;:';'+#####+''''''++++++++##+##+#####################++++++++++++++++++++#####@@#####@@###';:::::::;;;;''';
:::::::::::;';;+#@@@#+''''''++++++++++++++#######################++++++++++++++++++++####@######@####;:::::::;;;''';'
::::::::::,;:':+##@#++''''''++++++++++++#######################+#++++++++++++++++++++#########@####@#':::::::::;';;''
::::::::::,::+'+####+'''''''++++++++++++++#+###################+++++++++++++++++++++++###########@#@##::::::::::;'';'
::::::::::,:'''#+###++'''++'++++++++++++++++#+###############+#++++++++++++++++++++++++########@@@#@@+;::;:::::::;'''
::::::::::::;#'+####++''''''+++++++++++++++##########+##++###+++++++#++++++++++++++++++########@##@##+':;;;;::::::;;;
,::,::::::::'#++####++''''+'+++++++++++++++++########+#+++++++++++#+++++++++++++++++++++#######@@@###++;:;;;;;:::;:;;
,,,,,,::::::'#+'####++'''''+'++++++++++++++#######+++++++++++###++##++++++++++++++++++++#####@##@###++#';;;;::::::::;
:::,,:,::::;'+#;+###+'''''+++++++++++++++++#+++#++++++++++++####+####+++++++++++++++++++#####@@#@####+++;;;;;;;;:::::
,:,,,,,,:::'++##+###+''''''++++++++++++++++++++++++++++++++##########+##++++++++++++++++#####@#@####+++';;;;;;;:::::;
::,:,,,,,::;+#######+'''''+++++++++++++++++++++++++++++++++################++++++++++++++####@@@@##+++#++;;;;;:::;;:;
:::,::,,,,:''+#####++'+'''+++++++++++++++++++++++++++++++##############+++###++++++++++++####@@@##+++++++;;;;;;::::::
::::::,,,::+++######+''''''''++++++++++++++++++++++++++###########+++++#+++++#+++++++++++#####@#@#+#'++++'';;;;;;;:::
:::::::,:::;+#######+''+';''++++++++++++++++++++++++++###########++++++'+++++++++++++++++####@@@@#++++++++';;;;;;;;;:
::::::::,:::+#######+'''';'''+++++++++++++++++++++++#########@#++'''''''''''++++++++++++++####@@@###+#+++++;;;;';;::;
:::::::::::,'#######+''+'''''+++++++++++++++++++++++#########+'++'''+''''''''+++++++++++++####@@@@##+######+;;;;;;;;;
:::::::::::,:+######+'''''''''+'+++++++++++++++++++########+++++#######++'''''+++++++++++++####@@@##+++#####';;;;;;;;
:::::::::::::;######+''''';'''+++++++++++++++++++++###++++++++###########+++'++++++++++++++####@@@#++++####+';;;;;;;:
::::::::::::::++####+'''+';;''+++++++++++++++++++++++++++'++###########+##+++++++++++++++++#####@@#++++###++';;;;;;;;
::::::::::::::;#####+'''+';:;''++++++++++++'+++++'+++''''+#######@@@######+++++++++++++++++#####@@#+++'##++''';';;;;;
::::::::::::::::####+''''';;''+'+++++++++'++'+'+'+++'''+++########@@@######+++++++++++++++++####@@#+++'##+'''+'';';;;
::::::::::::::::'++###'''';;'+++++++++++++'''++++'''''+++#####+###@@@@##+######+++++++++++++###@@##++++##+';+'';';;;;
:::::::::::::::::##+##'''';''+++++++++'++'+'++++'''+'++++#####+#@#@###++++++###++++++++++++++###@##++++#+'';''+;;';;;
:::::::::::::::::;+++#+'''+'+#++###++++'''+++++++''+++++########@###+++++++###++++++++++++++####@###+++++'''''#+;;;;;
::::::::::::::::::;'###;'+'+##+###+++++'''++++++++++++++###@######++++++++##+++++++++++++++++####@##+''+'''''+#+:;;''
:::::::::::::::::::;;##''++'+#####++++++'''+++++++++++++########+++'''+++#####+++++++++++++++#######+'+++''';#@#;;'';
;;:;:;:::::::::::::::;++'++######+++'+'''''+++++++++++########+++''''+++##+++++++++++++++++++#@@@@##++++++''+###;:;''
;;;;;;;:::::::::::::;;'''++#+++''++###+++++++++++++++#########+++++++++++++++++++++++++++++++#@@#@##+++++++'+@##;::;;
::::;;;;;::::::::::::;':'++'';''##########+++++++++++############+++++++++++++++++++++++++++++#@#@@@#++++++'#@##':::;
::::::;;;;;::::::::::;':'''';;+#############+++++++##############+++++++##+++++++++++++++++++###@#@#+++++++'#@##;:::;
::::::;;;;;;;;:::::::;;:;+';;'#+####@@@@@#@#+++++################++++####++++++++++++'+'+++++##@@###++++++'+#@@+::::;
::;:;:;;;;;;;;;;:::::';::;';;++##++##@@@@###+++++########################+++++++++++++''+++++#######+++++''##@@+:::::
`.,::::;;;;;;;:::;;;;';::;;;;'+@+++@@#@@####+++++++#########+++#+++##+++++++++++++++''''+++++#######++++''+###@#:::::
````.,::;;;;;;;;::::;';;;;;;;'####+##########+++++++########+++++++++++++++++++++++++'+'++++++######+++++++####+:::::
```````..,:;;;;;;;::;';;;;;;''#######+++#####+++++++++########++++++++++++++++++++++++++++++++####++++++++#####':::::
```````````.,::;;;;:;';;;;;;;++++##+++++++##+++++++##############++++++++++++++++++++++++++++++#++++++++++#####'::::,
```````````````.:::;;';;;;;;;+'''''''''+++##+++++#######++++++##++++++++++++++++++++'++++++++++++++++++#++#####;::::,
``````````````````.,;';;;;;;'''''''''''+++++++++++#+###++++++++++++++++++++++''++'+++'++++++++++++++++++#++###+;:::::
````````````````````::.,::;;';''''''''+++++++++++######++##++++++++++++++++++++++'++'++++++++++++++++++++####@'::::::
..``.....``...````.`;,.....:';'''''''+++++++++++++++#++++######++++++''+++'+'''+''++'++++++++++++++++++#+++###;::::::
;;:;;;;;::;;;:.:;:,:';;;;;;;;;'''+'++++++++++++++++++++#+#######++++'''''''''''''''++++++++++++++++++++++++##';::::::
;;;;;''';;;;;;;';;;;';;';;'''+''''++++++++++'++++++++++++#######++++++++'''''''''''''+++++++++++++++++++#+###;;::::::
;;;;';;;;;;;;;;;;;;;';;''''''''+++++++++++++'+++++++++++++#+++++#++++++++'''''''+''+''+'++++++++++++++++++###;;::::::
;;';';;;;;'';;;;'''''';'''''''+'+'++++++++++'++++++++++++++++++++++++++++'+++++''''++'+''++++++++++++++#++##';:::::::
''';'''''''';';'''''''''''''''#''++++++'++'''++++++++++++++++++'+++++++++++'+++++''++++++++++++++++++++#++##;;:::::::
''''''''''''''''''''''''''''''''''++++++++'''+++++++++''+++'''''#++++++++++++'++++'++++++++++++++++++++++##';;:::::::
;;''''''';'''''''''''''''''''''+'''+++++++'''+++++'+''''''';''+#+++###+++++++++'+++++++++++++#++++++++#++##;;;:::::::
::::::::::::::;;;;;'';;;;''''''''''''+++++'''+''+'''''''';+++##++######+++++++++++++++++++++++++++++++#####;;;:::::::
:::::::::::::::::::';:::::::::::''''''''''''''''''';'';'++++++##+####+#+#+++++++++++++++++++++++++++++####+;;;:::::::
::;::::::::::::::::';:::::::::;;;'''''''''''';;;;;;;''+'''++++#########+++++++++++++++++++++++++++++++++##';;;;;:::::
::;:::::::::;:;::::';;:::::::::;;;'''''''''';;;;;;;;;''''++++##########++++++++++++++++++++++++++++++#####';;;:;:::::
:;:::::::;;;:::;;;:';:;;;:::::;:;;''''''''''''+++';;'''''+++##########+++++'+++++++++++++++++++++++++#####';;;;;;::::
:;:::;;;;;::;:::::;':::;::;:::;:::;'''''''''++++++++'+++++++##+####+++++++'+#++++++++++++++++++++++++####+;;;;;;;;:::
:::::::::;:;::::;;;':::::::::::;;;;;''''''''++++++++++++++++++++#++++++'''####++++++++++++++++++++++#+###+;;;;;;;;;;:
:::;:::::::;::::::;'::::::::;:;;;;;;'''''''+++++++++++++++++++++++++++''+######+++++++++++++++++++++#####';;;;;;;;;;:
:::;;:::;;;;;;;:;;;':;::;::;;:;;;;::;''''''+++++++++++++++++++++++++++++@@######++++++++++++++++++++#####';;;;;;;;;;;
:::;;:::::;;;;::;;;';;::;::::::;;:::;;;;'''++++++++++++#####+++++++++++@####+###+++'+++++++++++++++######';;;;;;;;;;;
:::::::::;;::;:;;;;;;:::::;:::;::::::;;;'''++++++++++++#####++++++++#@###++#+#+++++++++++++++++++++#####+;;;;;;;;;;;;
::;;;;;;;;;;::;;;;';;;:::::::::;;;::::';'''++++++++++++###++++++++#######+++++++++++++++++++++++++######+;;;;;;;;;;;;
::;;;;;;;,:;:;;;;;';::::::;::;;;::::;::;'''+++++++++++++++++++++#######+++++++++++++++++++++++++++######';;;;;;;;;;;;
:;;;;;;::;:;:;;::;':;:;;;::::::::::::;;;'''''+'''''+++++++++++#@#####++++++++++++++++++++++++++++++#####';;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;'::::::::::;;;;;;;;:::'''''''';'''+++''+'+########++++++++++++++++++++++++++++++######';;;;;;;;;;;;
;;;;:::;;::::;:;;;'::::::;;:::;;:::;::::;'''''''+@#+++############++++++++++++++++++++++++++++++++#####+;;;;;;;;;;;;;
:;::::::::::::::::'::::::;;;;;;:::::::;;;;''''''+##############+++++++++++++++++++++++++++++++++++#####';;;;;;;;;;;;;
;:;::;;;;;::::;::;';;:;;;;;;;;;;::::::::;;;'''''+++#++#######++++'++'+++++++++++++++++++++++++++#######';;;;;;;;;;;;;
';;;:;;::;::;:::;'';:::;;::;::;:;::::::::::;'''++++++++###+++++'''''+'++++++++++##+++++++++++++++######;;;;;;;;;;;;;;
;;;::::::::;;;;;:;;::;;;::::::::::::::::::::''''+++'+++++++''''''+'''++++++++++#++#+++++++++++++##+###+;;;;;;;;;;;;;;
:::,:::;::::::;;;;;:;:::::;;:,::::::::;:::;::''+++++''''''''''''+'''''+++++#++#+#+++#+++++++++++++#+##';;;;;;;;;;;;;;
:::::::;;::::::::;;;;;;:;;:::;;;:;;;::;:::;;;;''++++'''''''''''''+''++++++++#######+++++++++++++++++##';;;;;;;;;;;;;;
;;;;;;;;';;;;;;''';;;;;;;;::::::;;;;;::::;::;;;''++++''''''''''''+++++++++##+######+#++++++++++++++#+#';;;;;;;;;;;;;;
:::,:,::;;:::::::',::::,,:;;;;;;;''';;;;:;;;:,;;''+++''''''''++++++++++++##########++++++++++++++++##+;;;;;;;;;;;;;;;
:::::::::;:::::::':::::::,:;;;;;:::::;;;;;::;:;;;''+''''''''+++++++++#+###+#########+++++++++++++++##';;;;;;;;;;;;;;;
:::::::;;;;;::::;'::;;;::;::::::::::;;;;:::::;:;;;''+''''''+++++++#+++##+#######++++++++++++++++++++#;;;;;;;;;;;;;;;;
:::::::;;;;:::;;;';:::::;;::;;;;;;:;;;;;';;;;;;:;;;'''++''+++++++##+++#+#####+##+##++++++++++++++++++;;;;;;;;;;;;;;;;
:;;;::;::::;;;;;;;:::::;;;::::::;;;;;;;;;;;;;;;;'''''+++++++++++###+##++##+#####++#+++++'++++++++++++;;;;;;;;;;;;;;;;
::;;:::;:::::;;;';;;;:;;;;;;;:::::::::::;:::;;;;';;;'++++++++++++++++++++#####+++++++++'''++++++++++';;;;;;;;;;;;;;;;
::::,:::::;;;;;:;;::::::::::;:::::;;;;;;;;;;;''''''';;'+++++++++++++++++++++++++++++++'''''++++++++#';;;;;;;;;;;;;;;;
;;:::::::;::;;::';;;::::,::;;;;::::;;:;:;;;::;;;;;;;::'++++++++++++++++++++++++++++++'''''++++++++++;;;;;;;;;;;;;;;;;
:::::::::::;::::;::::::::::;:::;;;::;;;:::;'';;;;;;;::;+++++++++++++++++++++++++++++'''''''+++++++++;;;;;;;;;;;;;;;;;
;;;::;;:::::::::'::::;;';;::;;:::::::;;;;;;;;;';;;;;;;:;++++++++'''+++++++++++++++++''''''''+++++++';;;;;;;;;;;;;;;;;
::::::::::::::;;'::;;;;:;::::;;;;::::::::::::;;;;;;:::,,++++++++'''''''+++++++++'+';''''''''''+++++;;;;;;;;;;;;;;;;;;
::;;;;;;;;;::;';';;;;;;''';'';;:::::::::,,:::;:::::::,,,,++++'+'''''+''''++++++++''''''''''''''++++;;;;;;;;;;;;;;;;;;
;;;';;;;;;;''+'''''''''++++''';;;;;;''';;;;;::::;::,,,,,,:'+'''''''''''''''+++''';''''''''''''''+++;;;::;;;;;;;;;;;;;
::;::;;;;;;;''''';;;;;;;';;''''':;:;';;;;;;;::;:::::,,,,,,;'''''''''''''''''''';;;'''''''''''''+'+';;;::;;;;;;;;;;;;;
;;;;;::;:;;;;;;;;;;;;;;;;;;;;;;::;;;;;''''';;;,,;;;:,,,,,,,;''''''''''''''';;;;;;''''''''''''''''+;;;:;:::::;;;;:;:::
;::::::::::::;;;;;;;;;'''''';:;;;;;;;;;;;;;;;;:;:::,,,,,,,,,:'';'''''';:,:::;;;;';'''''''''''''''':;::;;:::::;:::;;;;
;::::::::;:;;;;;:;;;:::;'':;;:::::::;;;;;;:::::::::,,,,,,,,,.`.:;::,.. ..;;:;;';;;;;';'''''''''''';::::::::;;;::::;;;
:,,::::::;;;;;:;::;;;;;+:':::::::;::;;:::::::;;;;',,,,,,,,,,.``````.`. `,:;;;''';;;;;;'''''''''''':::::::::::::::::::
:::::::::::::;;;;;;;;;;;'';;::::,,:::::::::;;'';::,,,,,,,,,.``````.`.` `,:;;;''';';;;'''''''''''';:::::::::::::::::::
;::,,,:::::::;;;'';;;:::'';::::;;';;;:::;;;;;;;'',,,,,,,,,.```````.`````,::;;'';;'';;;'''''''''''::::::::::::::::::::
,,::,,,,,,,,:::':::::;:+;'';:::::::;;;;:;'''';';;,,,,,,,,,.```` ..`..` `.::;;'';;;'';'''''''''+''::::::::::::::::::::
::::,::;;;::::;';::::,,+'''::::;::;;;;;;'''''''':,,,,,,,,.```````.`..```.:::;'';;;'''';'''''''++'::::::::::::::::::::
:::::,,:::::;;';;;;;;;;+''':::,,:::::;;;;;;;;;;;,,,,,,,,..````````...` `.::`;'';;;'''';''''''''':::::::::::::::::::::
:;;;;;;;::;;;;';;::::::++''::;;;;;;::::::;::::::,,,,,,,,.`````````...` `.,``:'';;;;''';''''''''':::::::::::::::::::::
;;::::::::::::;;::::;;;++''::::;;;;;;;::::::::::,,,,,,,.``````````...` `,. .:';;;;;'''''++'''''+:::::::::::::::::::::
''''';';;::;:;';;;;''''++'';;:;;::;::::::;;;;;;;,,,,,,,.`````````....` `.``.:;;;;;;''+''++++'''+:::::::::::::::::::::
''''''';:;;;;';'''''';;++;';'';;;;;';;::::::::;;,,,,,,,.`````````....` `` ``,;;;;;;''''''+++++++:::::::::::::::::::::
:;;';;::::;;;;;;;:;;;;;'+;'::;;;++';:::::;;;;;'',,,,,,.````````......```  ``.;;;;;;''+'''+++++'':::::::::::::::::::::
;::::::;::;;;;':::::::;'+;'::::;;::::::,::::::;:,,,,,,.`````````.....```  ``,;;;;;''''''+++++++::::::::::::::::::::::
:::;;;:;::;;;'':::::;;;'+:'::,,,,:,,::;;;;;;';;,,,,,,.`````` `.`....````   `,';;;;;''++++++++++:,::::::::::::::::::::
;:::;:;,,::;:;':::;;''''+:'''''';:::;'''';:::;;,,,,,,.````` ``......````   `:';;;;;''+++++++++:::::::::::::::::::::::
;;;;:;:::::::;;::::::::;+:';:;;::;;;;::;;;;;:::,,,,,,.```````.`......``` ```:;;;;;;;''++++++++::,::::::::::::::::::::
,,,::::;;::::;';;;;::::;+:'::::::::::::::::;'';,,,,,..`````````.....``` ` `.:';;;;;;'++#+++++::::,:,:::::::::::::::::
;;;:::::::,,:;;:::::,::;+:';;:;;;:::::::::,:::,,,,,,.```` ````......```   ``:;;;;;;;'++++++++::::,,,:::::::::::::::::
';;'+;;::,,,,;;;;;;;;;::+:';:,,,:,:::::::,:,,,,,,,,,.````````````...```   ``:;;;;;;;'+++++++,:::,,,,:::::::::::::::::
;;;''+'''';;;;::::::;;;'+:''';;::;:::::,:::::::,,,,.``` ````````.`..````  `.,;;;;;;;'+++#++'::::,,,::::::::::::::::::
;'''''''+++++;''';''''''+;';;;;;;::;;:;:,:,:::;,,,,.``````````````..````` ``,;;;;;;;'+++#+#:::::,:::::::::::::::::::,
;'''''''''''';;;;;;;;;::+;'';;::::::'';;::::,:::,,,.````  ```````...````  ``.;;;;;;;'+++++::::::::::::::::::::::::::,
:;::::;:;;';;;::::;;;;;'+;''::;;;;:;;:;;;'''';':,,,.`` `````````....```  ```.;;;;;;;'+++#'::::::::::::::::::::::::::,
Author: Chris Kauffman (kauffman@cs.gmu.edu)
Date: 2017-09-11 Mon 14:08