diff options
Diffstat (limited to 'opendc-trace')
9 files changed, 611 insertions, 0 deletions
diff --git a/opendc-trace/build.gradle.kts b/opendc-trace/build.gradle.kts new file mode 100644 index 00000000..7edfd134 --- /dev/null +++ b/opendc-trace/build.gradle.kts @@ -0,0 +1,21 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ diff --git a/opendc-trace/opendc-trace-gwf/build.gradle.kts b/opendc-trace/opendc-trace-gwf/build.gradle.kts new file mode 100644 index 00000000..f3dfd6ef --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/build.gradle.kts @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +description = "Support for GWF traces in OpenDC" + +/* Build configuration */ +plugins { + `kotlin-library-conventions` + `testing-conventions` + `jacoco-conventions` +} + +dependencies { + api(platform(projects.opendcPlatform)) + api(projects.opendcTrace.opendcTraceApi) + + implementation(libs.jackson.dataformat.csv) +} diff --git a/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTable.kt b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTable.kt new file mode 100644 index 00000000..80a99d10 --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTable.kt @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.trace.gwf + +import com.fasterxml.jackson.dataformat.csv.CsvFactory +import org.opendc.trace.* +import java.net.URL + +/** + * A [Table] containing the tasks in a GWF trace. + */ +internal class GwfTaskTable(private val factory: CsvFactory, private val url: URL) : Table { + override val name: String = TABLE_TASKS + + override val isSynthetic: Boolean = false + + override fun isSupported(column: TableColumn<*>): Boolean { + return when (column) { + TASK_WORKFLOW_ID -> true + TASK_ID -> true + TASK_SUBMIT_TIME -> true + TASK_RUNTIME -> true + TASK_REQ_NCPUS -> true + TASK_ALLOC_NCPUS -> true + TASK_PARENTS -> true + else -> false + } + } + + override fun newReader(): TableReader { + return GwfTaskTableReader(factory.createParser(url)) + } + + override fun newReader(partition: String): TableReader { + throw IllegalArgumentException("Invalid partition $partition") + } + + override fun toString(): String = "GwfTaskTable" +} diff --git a/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTableReader.kt b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTableReader.kt new file mode 100644 index 00000000..64b7d465 --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTaskTableReader.kt @@ -0,0 +1,211 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.trace.gwf + +import com.fasterxml.jackson.core.JsonToken +import com.fasterxml.jackson.dataformat.csv.CsvParser +import com.fasterxml.jackson.dataformat.csv.CsvSchema +import org.opendc.trace.* +import java.util.regex.Pattern + +/** + * A [TableReader] implementation for the GWF format. + */ +internal class GwfTaskTableReader(private val parser: CsvParser) : TableReader { + /** + * The current parser state. + */ + private val state = RowState() + + init { + parser.schema = schema + } + + override fun nextRow(): Boolean { + // Reset the row state + state.reset() + + if (!nextStart()) { + return false + } + + while (true) { + val token = parser.nextValue() + + if (token == null || token == JsonToken.END_OBJECT) { + break + } + + when (parser.currentName) { + "WorkflowID" -> state.workflowId = parser.longValue + "JobID" -> state.jobId = parser.longValue + "SubmitTime" -> state.submitTime = parser.longValue + "RunTime" -> state.runtime = parser.longValue + "NProcs" -> state.nProcs = parser.intValue + "ReqNProcs" -> state.reqNProcs = parser.intValue + "Dependencies" -> parseParents(parser.valueAsString) + } + } + + return true + } + + override fun hasColumn(column: TableColumn<*>): Boolean { + return when (column) { + TASK_WORKFLOW_ID -> true + TASK_ID -> true + TASK_SUBMIT_TIME -> true + TASK_RUNTIME -> true + TASK_REQ_NCPUS -> true + TASK_ALLOC_NCPUS -> true + TASK_PARENTS -> true + else -> false + } + } + + override fun <T> get(column: TableColumn<T>): T { + val res: Any = when (column) { + TASK_WORKFLOW_ID -> state.workflowId + TASK_ID -> state.jobId + TASK_SUBMIT_TIME -> state.submitTime + TASK_RUNTIME -> state.runtime + TASK_REQ_NCPUS -> state.nProcs + TASK_ALLOC_NCPUS -> state.reqNProcs + TASK_PARENTS -> state.dependencies + else -> throw IllegalArgumentException("Invalid column") + } + + @Suppress("UNCHECKED_CAST") + return res as T + } + + override fun getBoolean(column: TableColumn<Boolean>): Boolean { + throw IllegalArgumentException("Invalid column") + } + + override fun getInt(column: TableColumn<Int>): Int { + return when (column) { + TASK_REQ_NCPUS -> state.nProcs + TASK_ALLOC_NCPUS -> state.reqNProcs + else -> throw IllegalArgumentException("Invalid column") + } + } + + override fun getLong(column: TableColumn<Long>): Long { + return when (column) { + TASK_WORKFLOW_ID -> state.workflowId + TASK_ID -> state.jobId + TASK_SUBMIT_TIME -> state.submitTime + TASK_RUNTIME -> state.runtime + else -> throw IllegalArgumentException("Invalid column") + } + } + + override fun getDouble(column: TableColumn<Double>): Double { + throw IllegalArgumentException("Invalid column") + } + + override fun close() { + parser.close() + } + + /** + * The pattern used to parse the parents. + */ + private val pattern = Pattern.compile("\\s+") + + /** + * Parse the parents into a set of longs. + */ + private fun parseParents(value: String): Set<Long> { + val result = mutableSetOf<Long>() + val deps = value.split(pattern) + + for (dep in deps) { + if (dep.isBlank()) { + continue + } + + result.add(dep.toLong(10)) + } + + return result + } + + /** + * Advance the parser until the next object start. + */ + private fun nextStart(): Boolean { + var token = parser.nextValue() + + while (token != null && token != JsonToken.START_OBJECT) { + token = parser.nextValue() + } + + return token != null + } + + /** + * The current row state. + */ + private class RowState { + var workflowId = -1L + var jobId = -1L + var submitTime = -1L + var runtime = -1L + var nProcs = -1 + var reqNProcs = -1 + var dependencies = emptySet<Long>() + + /** + * Reset the state. + */ + fun reset() { + workflowId = -1 + jobId = -1 + submitTime = -1 + runtime = -1 + nProcs = -1 + reqNProcs = -1 + dependencies = emptySet() + } + } + + companion object { + /** + * The [CsvSchema] that is used to parse the trace. + */ + private val schema = CsvSchema.builder() + .addColumn("WorkflowID", CsvSchema.ColumnType.NUMBER) + .addColumn("JobID", CsvSchema.ColumnType.NUMBER) + .addColumn("SubmitTime", CsvSchema.ColumnType.NUMBER) + .addColumn("RunTime", CsvSchema.ColumnType.NUMBER) + .addColumn("NProcs", CsvSchema.ColumnType.NUMBER) + .addColumn("ReqNProcs", CsvSchema.ColumnType.NUMBER) + .addColumn("Dependencies", CsvSchema.ColumnType.STRING) + .setAllowComments(true) + .setUseHeader(true) + .setColumnSeparator(',') + .build() + } +} diff --git a/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTrace.kt b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTrace.kt new file mode 100644 index 00000000..166c1e56 --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTrace.kt @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.trace.gwf + +import com.fasterxml.jackson.dataformat.csv.CsvFactory +import org.opendc.trace.* +import java.net.URL + +/** + * [Trace] implementation for the GWF format. + */ +public class GwfTrace internal constructor(private val factory: CsvFactory, private val url: URL) : Trace { + override val tables: List<String> = listOf(TABLE_TASKS) + + override fun containsTable(name: String): Boolean = TABLE_TASKS == name + + override fun getTable(name: String): Table? { + if (!containsTable(name)) { + return null + } + + return GwfTaskTable(factory, url) + } + + override fun toString(): String = "GwfTrace[$url]" +} diff --git a/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTraceFormat.kt b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTraceFormat.kt new file mode 100644 index 00000000..6d542503 --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/main/kotlin/org/opendc/trace/gwf/GwfTraceFormat.kt @@ -0,0 +1,56 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.trace.gwf + +import com.fasterxml.jackson.dataformat.csv.CsvFactory +import com.fasterxml.jackson.dataformat.csv.CsvParser +import org.opendc.trace.spi.TraceFormat +import java.net.URL +import java.nio.file.Paths +import kotlin.io.path.exists + +/** + * A [TraceFormat] implementation for the GWF trace format. + */ +public class GwfTraceFormat : TraceFormat { + /** + * The name of this trace format. + */ + override val name: String = "gwf" + + /** + * The [CsvFactory] used to create the parser. + */ + private val factory = CsvFactory() + .enable(CsvParser.Feature.ALLOW_COMMENTS) + .enable(CsvParser.Feature.TRIM_SPACES) + + /** + * Read the tasks in the GWF trace. + */ + public override fun open(url: URL): GwfTrace { + val path = Paths.get(url.toURI()) + require(path.exists()) { "URL $url does not exist" } + return GwfTrace(factory, url) + } +} diff --git a/opendc-trace/opendc-trace-gwf/src/main/resources/META-INF/services/org.opendc.trace.spi.TraceFormat b/opendc-trace/opendc-trace-gwf/src/main/resources/META-INF/services/org.opendc.trace.spi.TraceFormat new file mode 100644 index 00000000..99a874c8 --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/main/resources/META-INF/services/org.opendc.trace.spi.TraceFormat @@ -0,0 +1 @@ +org.opendc.trace.gwf.GwfTraceFormat diff --git a/opendc-trace/opendc-trace-gwf/src/test/kotlin/org/opendc/trace/gwf/GwfTraceFormatTest.kt b/opendc-trace/opendc-trace-gwf/src/test/kotlin/org/opendc/trace/gwf/GwfTraceFormatTest.kt new file mode 100644 index 00000000..6b0568fe --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/test/kotlin/org/opendc/trace/gwf/GwfTraceFormatTest.kt @@ -0,0 +1,109 @@ +/* + * Copyright (c) 2021 AtLarge Research + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +package org.opendc.trace.gwf + +import org.junit.jupiter.api.Assertions.* +import org.junit.jupiter.api.Test +import org.junit.jupiter.api.assertAll +import org.junit.jupiter.api.assertDoesNotThrow +import org.junit.jupiter.api.assertThrows +import org.opendc.trace.* +import java.net.URL + +/** + * Test suite for the [GwfTraceFormat] class. + */ +internal class GwfTraceFormatTest { + @Test + fun testTraceExists() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + assertDoesNotThrow { + format.open(input) + } + } + + @Test + fun testTraceDoesNotExists() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + assertThrows<IllegalArgumentException> { + format.open(URL(input.toString() + "help")) + } + } + + @Test + fun testTables() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + val trace = format.open(input) + + assertEquals(listOf(TABLE_TASKS), trace.tables) + } + + @Test + fun testTableExists() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + val table = format.open(input).getTable(TABLE_TASKS) + + assertNotNull(table) + assertDoesNotThrow { table!!.newReader() } + } + + @Test + fun testTableDoesNotExist() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + val trace = format.open(input) + + assertFalse(trace.containsTable("test")) + assertNull(trace.getTable("test")) + } + + @Test + fun testTableReader() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + val table = format.open(input).getTable(TABLE_TASKS)!! + val reader = table.newReader() + + assertAll( + { assertTrue(reader.nextRow()) }, + { assertEquals(0L, reader.getLong(TASK_WORKFLOW_ID)) }, + { assertEquals(1L, reader.getLong(TASK_ID)) }, + { assertEquals(16, reader.getLong(TASK_SUBMIT_TIME)) }, + { assertEquals(11, reader.getLong(TASK_RUNTIME)) }, + { assertEquals(setOf<Long>(), reader.get(TASK_PARENTS)) }, + ) + } + + @Test + fun testTableReaderPartition() { + val input = checkNotNull(GwfTraceFormatTest::class.java.getResource("/trace.gwf")) + val format = GwfTraceFormat() + val table = format.open(input).getTable(TABLE_TASKS)!! + + assertThrows<IllegalArgumentException> { table.newReader("test") } + } +} diff --git a/opendc-trace/opendc-trace-gwf/src/test/resources/trace.gwf b/opendc-trace/opendc-trace-gwf/src/test/resources/trace.gwf new file mode 100644 index 00000000..2f99616d --- /dev/null +++ b/opendc-trace/opendc-trace-gwf/src/test/resources/trace.gwf @@ -0,0 +1,71 @@ +WorkflowID, JobID , SubmitTime, RunTime , NProcs , ReqNProcs , Dependencies +0 , 1 , 16 , 11 , 1 , 1 , +0 , 2 , 40 , 11 , 1 , 1 , 1 +0 , 3 , 40 , 11 , 1 , 1 , 1 +0 , 4 , 64 , 11 , 1 , 1 , 2 +0 , 5 , 63 , 11 , 1 , 1 , 3 +0 , 6 , 64 , 11 , 1 , 1 , 3 +0 , 7 , 87 , 11 , 1 , 1 , 4 5 6 +1 , 8 , 4 , 11 , 1 , 1 , +1 , 9 , 15 , 11 , 1 , 1 , 8 +1 , 10 , 15 , 11 , 1 , 1 , 8 +1 , 11 , 27 , 11 , 1 , 1 , 9 +1 , 12 , 27 , 11 , 1 , 1 , 10 +1 , 13 , 27 , 11 , 1 , 1 , 10 +1 , 14 , 38 , 11 , 1 , 1 , 12 11 13 +2 , 15 , 3 , 11 , 1 , 1 , +2 , 16 , 27 , 11 , 1 , 1 , 15 +2 , 17 , 27 , 11 , 1 , 1 , 15 +2 , 18 , 52 , 11 , 1 , 1 , 16 +2 , 19 , 51 , 11 , 1 , 1 , 17 +2 , 20 , 51 , 11 , 1 , 1 , 17 +2 , 21 , 75 , 11 , 1 , 1 , 20 18 19 +3 , 22 , 3 , 11 , 1 , 1 , +3 , 23 , 27 , 11 , 1 , 1 , 22 +3 , 24 , 27 , 11 , 1 , 1 , 22 +3 , 25 , 51 , 11 , 1 , 1 , 23 +3 , 26 , 50 , 11 , 1 , 1 , 24 +3 , 27 , 51 , 11 , 1 , 1 , 24 +3 , 28 , 75 , 11 , 1 , 1 , 25 27 26 +4 , 29 , 3 , 11 , 1 , 1 , +4 , 30 , 27 , 11 , 1 , 1 , 29 +4 , 31 , 27 , 11 , 1 , 1 , 29 +4 , 32 , 50 , 11 , 1 , 1 , 30 +4 , 33 , 50 , 11 , 1 , 1 , 31 +4 , 34 , 51 , 11 , 1 , 1 , 31 +4 , 35 , 74 , 11 , 1 , 1 , 33 32 34 +5 , 36 , 3 , 11 , 1 , 1 , +5 , 37 , 27 , 11 , 1 , 1 , 36 +5 , 38 , 26 , 11 , 1 , 1 , 36 +5 , 39 , 51 , 11 , 1 , 1 , 37 +5 , 40 , 50 , 11 , 1 , 1 , 38 +5 , 41 , 50 , 11 , 1 , 1 , 38 +5 , 42 , 74 , 11 , 1 , 1 , 39 40 41 +6 , 43 , 4 , 11 , 1 , 1 , +6 , 44 , 27 , 11 , 1 , 1 , 43 +6 , 45 , 27 , 11 , 1 , 1 , 43 +6 , 46 , 51 , 11 , 1 , 1 , 44 +6 , 47 , 51 , 11 , 1 , 1 , 45 +6 , 48 , 51 , 11 , 1 , 1 , 45 +6 , 49 , 75 , 11 , 1 , 1 , 46 47 48 +7 , 50 , 3 , 0 , 1 , 1 , +7 , 51 , 17 , 0 , 1 , 1 , 50 +7 , 52 , 17 , 0 , 1 , 1 , 50 +7 , 53 , 30 , 0 , 1 , 1 , 51 +7 , 54 , 30 , 0 , 1 , 1 , 52 +7 , 55 , 31 , 0 , 1 , 1 , 52 +7 , 56 , 44 , 0 , 1 , 1 , 55 54 53 +8 , 57 , 3 , 11 , 1 , 1 , +8 , 58 , 26 , 11 , 1 , 1 , 57 +8 , 59 , 27 , 11 , 1 , 1 , 57 +8 , 60 , 50 , 11 , 1 , 1 , 58 +8 , 61 , 51 , 11 , 1 , 1 , 59 +8 , 62 , 50 , 11 , 1 , 1 , 59 +8 , 63 , 74 , 11 , 1 , 1 , 62 61 60 +9 , 64 , 3 , 11 , 1 , 1 , +9 , 65 , 27 , 11 , 1 , 1 , 64 +9 , 66 , 27 , 11 , 1 , 1 , 64 +9 , 67 , 51 , 11 , 1 , 1 , 65 +9 , 68 , 50 , 11 , 1 , 1 , 66 +9 , 69 , 51 , 11 , 1 , 1 , 66 +9 , 70 , 74 , 11 , 1 , 1 , 68 69 67 |