copy (zstd only) unit tests from airlift repository

23 files changed, 2409 insertions, 0 deletions

diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/AbstractTestCompression.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/AbstractTestCompression.java
new file mode 100644
index 00000000000..c8d530bc238
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/AbstractTestCompression.java
@@ -0,0 +1,626 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import com.google.common.primitives.Bytes;
+import ai.vespa.airlift.compress.benchmark.DataSet;
+import org.testng.SkipException;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Guice;
+import org.testng.annotations.Test;
+
+import javax.inject.Inject;
+
+import java.io.IOException;
+import java.io.UncheckedIOException;
+import java.nio.Buffer;
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
+
+import static com.google.common.base.Preconditions.checkPositionIndexes;
+import static java.lang.System.arraycopy;
+import static java.nio.charset.StandardCharsets.UTF_8;
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+import static org.assertj.core.api.Assertions.catchThrowable;
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.fail;
+
+@Guice(modules = TestingModule.class)
+public abstract class AbstractTestCompression
+{
+    private List<DataSet> testCases;
+
+    protected abstract Compressor getCompressor();
+
+    protected abstract Decompressor getDecompressor();
+
+    protected abstract Compressor getVerifyCompressor();
+
+    protected abstract Decompressor getVerifyDecompressor();
+
+    protected boolean isByteBufferSupported()
+    {
+        return true;
+    }
+
+    @Inject
+    public void setup(List<DataSet> dataSets)
+    {
+        testCases = new ArrayList<>();
+
+        testCases.add(new DataSet("nothing", new byte[0]));
+        testCases.add(new DataSet("short literal", "hello world!".getBytes(UTF_8)));
+        testCases.add(new DataSet("small copy", "XXXXabcdabcdABCDABCDwxyzwzyz123".getBytes(UTF_8)));
+        testCases.add(new DataSet("long copy", "XXXXabcdefgh abcdefgh abcdefgh abcdefgh abcdefgh abcdefgh ABC".getBytes(UTF_8)));
+
+        byte[] data = new byte[256];
+        for (int i = 0; i < data.length; i++) {
+            data[i] = (byte) i;
+        }
+        testCases.add(new DataSet("long literal", data));
+
+        testCases.addAll(dataSets);
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompress(DataSet dataSet)
+            throws Exception
+    {
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+        byte[] compressed = prepareCompressedData(uncompressedOriginal);
+
+        byte[] uncompressed = new byte[uncompressedOriginal.length];
+
+        Decompressor decompressor = getDecompressor();
+        int uncompressedSize = decompressor.decompress(
+                compressed,
+                0,
+                compressed.length,
+                uncompressed,
+                0,
+                uncompressed.length);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressedSize, uncompressedOriginal, 0, uncompressedOriginal.length);
+    }
+
+    // Tests that decompression works correctly when the decompressed data does not span the entire output buffer
+    @Test(dataProvider = "data")
+    public void testDecompressWithOutputPadding(DataSet dataSet)
+    {
+        int padding = 1021;
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+        byte[] compressed = prepareCompressedData(uncompressedOriginal);
+
+        byte[] uncompressed = new byte[uncompressedOriginal.length + 2 * padding]; // pre + post padding
+
+        Decompressor decompressor = getDecompressor();
+        int uncompressedSize = decompressor.decompress(
+                compressed,
+                0,
+                compressed.length,
+                uncompressed,
+                padding,
+                uncompressedOriginal.length + padding);
+
+        assertByteArraysEqual(uncompressed, padding, uncompressedSize, uncompressedOriginal, 0, uncompressedOriginal.length);
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompressionBufferOverrun(DataSet dataSet)
+    {
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+        byte[] compressed = prepareCompressedData(uncompressedOriginal);
+
+        // add padding with random bytes that we can verify later
+        byte[] padding = new byte[100];
+        ThreadLocalRandom.current().nextBytes(padding);
+
+        byte[] uncompressed = Bytes.concat(new byte[uncompressedOriginal.length], padding);
+
+        Decompressor decompressor = getDecompressor();
+        int uncompressedSize = decompressor.decompress(
+                compressed,
+                0,
+                compressed.length,
+                uncompressed,
+                0,
+                uncompressedOriginal.length);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressedSize, uncompressedOriginal, 0, uncompressedOriginal.length);
+
+        // verify padding is intact
+        assertByteArraysEqual(padding, 0, padding.length, uncompressed, uncompressed.length - padding.length, padding.length);
+    }
+
+    @Test
+    public void testDecompressInputBoundsChecks()
+    {
+        byte[] data = new byte[1024];
+        new Random(1234).nextBytes(data);
+        Compressor compressor = getCompressor();
+        byte[] compressed = new byte[compressor.maxCompressedLength(data.length)];
+        int compressedLength = compressor.compress(data, 0, data.length, compressed, 0, compressed.length);
+
+        Decompressor decompressor = getDecompressor();
+        Throwable throwable;
+
+        // null input buffer
+        assertThatThrownBy(() -> decompressor.decompress(null, 0, compressedLength, data, 0, data.length))
+                .isInstanceOf(NullPointerException.class);
+
+        // mis-declared buffer size
+        byte[] compressedChoppedOff = Arrays.copyOf(compressed, compressedLength - 1);
+        throwable = catchThrowable(() -> decompressor.decompress(compressedChoppedOff, 0, compressedLength, data, 0, data.length));
+        if (throwable instanceof UncheckedIOException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+
+        // overrun because of offset
+        byte[] compressedWithPadding = new byte[10 + compressedLength - 1];
+        arraycopy(compressed, 0, compressedWithPadding, 10, compressedLength - 1);
+
+        throwable = catchThrowable(() -> decompressor.decompress(compressedWithPadding, 10, compressedLength, data, 0, data.length));
+        if (throwable instanceof UncheckedIOException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+    }
+
+    @Test
+    public void testDecompressOutputBoundsChecks()
+    {
+        byte[] data = new byte[1024];
+        new Random(1234).nextBytes(data);
+        Compressor compressor = getCompressor();
+        byte[] compressed = new byte[compressor.maxCompressedLength(data.length)];
+        int compressedLength = compressor.compress(data, 0, data.length, compressed, 0, compressed.length);
+        byte[] input = Arrays.copyOf(compressed, compressedLength);
+
+        Decompressor decompressor = getDecompressor();
+        Throwable throwable;
+
+        // null output buffer
+        assertThatThrownBy(() -> decompressor.decompress(input, 0, input.length, null, 0, data.length))
+                .isInstanceOf(NullPointerException.class);
+
+        // small buffer
+        assertThatThrownBy(() -> decompressor.decompress(input, 0, input.length, new byte[1], 0, 1))
+                .hasMessageMatching("All input was not consumed|attempt to write.* outside of destination buffer.*|Malformed input.*|Uncompressed length 1024 must be less than 1|Output buffer too small.*");
+
+        // mis-declared buffer size
+        throwable = catchThrowable(() -> decompressor.decompress(input, 0, input.length, new byte[1], 0, data.length));
+        if (throwable instanceof IndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+
+        // mis-declared buffer size with greater buffer
+        throwable = catchThrowable(() -> decompressor.decompress(input, 0, input.length, new byte[data.length - 1], 0, data.length));
+        if (throwable instanceof IndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompressByteBufferHeapToHeap(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        ByteBuffer compressed = ByteBuffer.wrap(prepareCompressedData(uncompressedOriginal));
+        ByteBuffer uncompressed = ByteBuffer.allocate(uncompressedOriginal.length);
+
+        getDecompressor().decompress(compressed, uncompressed);
+        ((Buffer) uncompressed).flip();
+
+        assertByteBufferEqual(ByteBuffer.wrap(uncompressedOriginal), uncompressed);
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompressByteBufferHeapToDirect(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        ByteBuffer compressed = ByteBuffer.wrap(prepareCompressedData(uncompressedOriginal));
+        ByteBuffer uncompressed = ByteBuffer.allocateDirect(uncompressedOriginal.length);
+
+        getDecompressor().decompress(compressed, uncompressed);
+        ((Buffer) uncompressed).flip();
+
+        assertByteBufferEqual(ByteBuffer.wrap(uncompressedOriginal), uncompressed);
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompressByteBufferDirectToHeap(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        ByteBuffer compressed = toDirectBuffer(prepareCompressedData(uncompressedOriginal));
+        ByteBuffer uncompressed = ByteBuffer.allocate(uncompressedOriginal.length);
+
+        getDecompressor().decompress(compressed, uncompressed);
+        ((Buffer) uncompressed).flip();
+
+        assertByteBufferEqual(ByteBuffer.wrap(uncompressedOriginal), uncompressed);
+    }
+
+    @Test(dataProvider = "data")
+    public void testDecompressByteBufferDirectToDirect(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        ByteBuffer compressed = toDirectBuffer(prepareCompressedData(uncompressedOriginal));
+        ByteBuffer uncompressed = ByteBuffer.allocateDirect(uncompressedOriginal.length);
+
+        getDecompressor().decompress(compressed, uncompressed);
+        ((Buffer) uncompressed).flip();
+
+        assertByteBufferEqual(ByteBuffer.wrap(uncompressedOriginal), uncompressed);
+    }
+
+    @Test(dataProvider = "data")
+    public void testCompress(DataSet testCase)
+            throws Exception
+    {
+        Compressor compressor = getCompressor();
+
+        byte[] originalUncompressed = testCase.getUncompressed();
+        byte[] compressed = new byte[compressor.maxCompressedLength(originalUncompressed.length)];
+
+        // attempt to compress slightly different data to ensure the compressor doesn't keep state
+        // between calls that may affect results
+        if (originalUncompressed.length > 1) {
+            byte[] output = new byte[compressor.maxCompressedLength(originalUncompressed.length - 1)];
+            compressor.compress(originalUncompressed, 1, originalUncompressed.length - 1, output, 0, output.length);
+        }
+
+        int compressedLength = compressor.compress(
+                originalUncompressed,
+                0,
+                originalUncompressed.length,
+                compressed,
+                0,
+                compressed.length);
+
+        verifyCompressedData(originalUncompressed, compressed, compressedLength);
+    }
+
+    @Test
+    public void testCompressInputBoundsChecks()
+    {
+        Compressor compressor = getCompressor();
+        int declaredInputLength = 1024;
+        int maxCompressedLength = compressor.maxCompressedLength(1024);
+        byte[] output = new byte[maxCompressedLength];
+        Throwable throwable;
+
+        // null input buffer
+        assertThatThrownBy(() -> compressor.compress(null, 0, declaredInputLength, output, 0, output.length))
+                .isInstanceOf(NullPointerException.class);
+
+        // mis-declared buffer size
+        throwable = catchThrowable(() -> compressor.compress(new byte[1], 0, declaredInputLength, output, 0, output.length));
+        if (throwable instanceof IndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+
+        // max too small
+        throwable = catchThrowable(() -> compressor.compress(new byte[declaredInputLength - 1], 0, declaredInputLength, output, 0, output.length));
+        if (throwable instanceof IndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+
+        // overrun because of offset
+        throwable = catchThrowable(() -> compressor.compress(new byte[declaredInputLength + 10], 11, declaredInputLength, output, 0, output.length));
+        if (throwable instanceof IndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+    }
+
+    @Test
+    public void testCompressOutputBoundsChecks()
+    {
+        Compressor compressor = getCompressor();
+        int minCompressionOverhead = compressor.maxCompressedLength(0);
+        byte[] input = new byte[minCompressionOverhead * 4 + 1024];
+        new Random(1234).nextBytes(input);
+        int maxCompressedLength = compressor.maxCompressedLength(input.length);
+        Throwable throwable;
+
+        // null output buffer
+        assertThatThrownBy(() -> compressor.compress(input, 0, input.length, null, 0, maxCompressedLength))
+                .isInstanceOf(NullPointerException.class);
+
+        // small buffer
+        assertThatThrownBy(() -> compressor.compress(input, 0, input.length, new byte[1], 0, 1))
+                .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*|Max output length must be larger than .*|Output buffer must be at least.*|Output buffer too small");
+
+        // mis-declared buffer size
+        throwable = catchThrowable(() -> compressor.compress(input, 0, input.length, new byte[1], 0, maxCompressedLength));
+        if (throwable instanceof ArrayIndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+
+        // mis-declared buffer size with buffer large enough to hold compression frame header (if any)
+        throwable = catchThrowable(() -> compressor.compress(input, 0, input.length, new byte[minCompressionOverhead * 2], 0, maxCompressedLength));
+        if (throwable instanceof ArrayIndexOutOfBoundsException) {
+            // OK
+        }
+        else {
+            assertThat(throwable)
+                    .hasMessageMatching(".*must not be greater than size.*|Invalid offset or length.*");
+        }
+    }
+
+    @Test(dataProvider = "data")
+    public void testCompressByteBufferHeapToHeap(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        Compressor compressor = getCompressor();
+
+        verifyCompressByteBuffer(
+                compressor,
+                ByteBuffer.wrap(uncompressedOriginal),
+                ByteBuffer.allocate(compressor.maxCompressedLength(uncompressedOriginal.length)));
+    }
+
+    @Test(dataProvider = "data")
+    public void testCompressByteBufferHeapToDirect(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        Compressor compressor = getCompressor();
+
+        verifyCompressByteBuffer(
+                compressor,
+                ByteBuffer.wrap(uncompressedOriginal),
+                ByteBuffer.allocateDirect(compressor.maxCompressedLength(uncompressedOriginal.length)));
+    }
+
+    @Test(dataProvider = "data")
+    public void testCompressByteBufferDirectToHeap(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        Compressor compressor = getCompressor();
+
+        verifyCompressByteBuffer(
+                compressor,
+                toDirectBuffer(uncompressedOriginal),
+                ByteBuffer.allocate(compressor.maxCompressedLength(uncompressedOriginal.length)));
+    }
+
+    @Test(dataProvider = "data")
+    public void testCompressByteBufferDirectToDirect(DataSet dataSet)
+            throws Exception
+    {
+        if (!isByteBufferSupported()) {
+            throw new SkipException("ByteBuffer not supported");
+        }
+
+        byte[] uncompressedOriginal = dataSet.getUncompressed();
+
+        Compressor compressor = getCompressor();
+
+        verifyCompressByteBuffer(
+                compressor,
+                toDirectBuffer(uncompressedOriginal),
+                ByteBuffer.allocateDirect(compressor.maxCompressedLength(uncompressedOriginal.length)));
+    }
+
+    private void verifyCompressByteBuffer(Compressor compressor, ByteBuffer expected, ByteBuffer compressed)
+    {
+        // attempt to compress slightly different data to ensure the compressor doesn't keep state
+        // between calls that may affect results
+        if (expected.remaining() > 1) {
+            ByteBuffer duplicate = expected.duplicate();
+            duplicate.get(); // skip one byte
+            compressor.compress(duplicate, ByteBuffer.allocate(((Buffer) compressed).remaining()));
+        }
+
+        compressor.compress(expected.duplicate(), compressed);
+        ((Buffer) compressed).flip();
+
+        ByteBuffer uncompressed = ByteBuffer.allocate(((Buffer) expected).remaining());
+
+        // TODO: validate with "control" decompressor
+        getDecompressor().decompress(compressed, uncompressed);
+        ((Buffer) uncompressed).flip();
+
+        assertByteBufferEqual(expected.duplicate(), uncompressed);
+    }
+
+    private void verifyCompressedData(byte[] originalUncompressed, byte[] compressed, int compressedLength)
+    {
+        byte[] uncompressed = new byte[originalUncompressed.length];
+        int uncompressedSize = getVerifyDecompressor().decompress(compressed, 0, compressedLength, uncompressed, 0, uncompressed.length);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressedSize, originalUncompressed, 0, originalUncompressed.length);
+    }
+
+    @Test
+    public void testRoundTripSmallLiteral()
+            throws Exception
+    {
+        byte[] data = new byte[256];
+        for (int i = 0; i < data.length; i++) {
+            data[i] = (byte) i;
+        }
+
+        Compressor compressor = getCompressor();
+        byte[] compressed = new byte[compressor.maxCompressedLength(data.length)];
+        byte[] uncompressed = new byte[data.length];
+
+        for (int i = 1; i < data.length; i++) {
+            try {
+                int written = compressor.compress(
+                        data,
+                        0,
+                        i,
+                        compressed,
+                        0,
+                        compressed.length);
+
+                int decompressedSize = getDecompressor().decompress(compressed, 0, written, uncompressed, 0, uncompressed.length);
+
+                assertByteArraysEqual(data, 0, i, uncompressed, 0, decompressedSize);
+                assertEquals(decompressedSize, i);
+            }
+            catch (MalformedInputException e) {
+                throw new RuntimeException("Failed with " + i + " bytes of input", e);
+            }
+        }
+    }
+
+    @DataProvider(name = "data")
+    public Object[][] getTestCases()
+            throws IOException
+    {
+        Object[][] result = new Object[testCases.size()][];
+
+        for (int i = 0; i < testCases.size(); i++) {
+            result[i] = new Object[] {testCases.get(i)};
+        }
+
+        return result;
+    }
+
+    public static void assertByteArraysEqual(byte[] left, int leftOffset, int leftLength, byte[] right, int rightOffset, int rightLength)
+    {
+        checkPositionIndexes(leftOffset, leftOffset + leftLength, left.length);
+        checkPositionIndexes(rightOffset, rightOffset + rightLength, right.length);
+
+        for (int i = 0; i < Math.min(leftLength, rightLength); i++) {
+            if (left[leftOffset + i] != right[rightOffset + i]) {
+                fail(String.format("Byte arrays differ at position %s: 0x%02X vs 0x%02X", i, left[leftOffset + i], right[rightOffset + i]));
+            }
+        }
+
+        assertEquals(leftLength, rightLength, String.format("Array lengths differ: %s vs %s", leftLength, rightLength));
+    }
+
+    private static void assertByteBufferEqual(ByteBuffer left, ByteBuffer right)
+    {
+        Buffer leftBuffer = left;
+        Buffer rightBuffer = right;
+
+        int leftPosition = leftBuffer.position();
+        int rightPosition = rightBuffer.position();
+        for (int i = 0; i < Math.min(leftBuffer.remaining(), rightBuffer.remaining()); i++) {
+            if (left.get(leftPosition + i) != right.get(rightPosition + i)) {
+                fail(String.format("Byte buffers differ at position %s: 0x%02X vs 0x%02X", i, left.get(leftPosition + i), right.get(rightPosition + i)));
+            }
+        }
+
+        assertEquals(leftBuffer.remaining(), rightBuffer.remaining(), String.format("Buffer lengths differ: %s vs %s", leftBuffer.remaining(), leftBuffer.remaining()));
+    }
+
+    private static ByteBuffer toDirectBuffer(byte[] data)
+    {
+        ByteBuffer direct = ByteBuffer.allocateDirect(data.length);
+        direct.put(data);
+
+        ((Buffer) direct).flip();
+
+        return direct;
+    }
+
+    private byte[] prepareCompressedData(byte[] uncompressed)
+    {
+        Compressor compressor = getVerifyCompressor();
+
+        byte[] compressed = new byte[compressor.maxCompressedLength(uncompressed.length)];
+
+        int compressedLength = compressor.compress(
+                uncompressed,
+                0,
+                uncompressed.length,
+                compressed,
+                0,
+                compressed.length);
+
+        return Arrays.copyOf(compressed, compressedLength);
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/ByteArrayOutputStream.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/ByteArrayOutputStream.java
new file mode 100644
index 00000000000..feb34b03869
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/ByteArrayOutputStream.java
@@ -0,0 +1,65 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import java.io.OutputStream;
+
+import static com.google.common.base.Preconditions.checkPositionIndex;
+
+public final class ByteArrayOutputStream
+        extends OutputStream
+{
+    private final byte[] buffer;
+    private final int initialOffset;
+    private final int bufferLimit;
+    private int offset;
+
+    public ByteArrayOutputStream(byte[] buffer)
+    {
+        this(buffer, 0, buffer.length);
+    }
+
+    public ByteArrayOutputStream(byte[] buffer, int offset, int length)
+    {
+        this.buffer = buffer;
+        this.initialOffset = offset;
+        this.bufferLimit = offset + length;
+        this.offset = offset;
+    }
+
+    @Override
+    public void write(int value)
+    {
+        checkPositionIndex(offset + 1, bufferLimit);
+        buffer[offset++] = (byte) value;
+    }
+
+    @Override
+    public void write(byte[] buffer, int offset, int length)
+    {
+        checkPositionIndex(this.offset + length, bufferLimit);
+        System.arraycopy(buffer, offset, this.buffer, this.offset, length);
+        this.offset += length;
+    }
+
+    public int size()
+    {
+        return offset - initialOffset;
+    }
+
+    public byte[] getBuffer()
+    {
+        return buffer;
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecCompressor.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecCompressor.java
new file mode 100644
index 00000000000..3511c9972d8
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecCompressor.java
@@ -0,0 +1,65 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import org.apache.hadoop.io.compress.CompressionCodec;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.io.UncheckedIOException;
+import java.nio.ByteBuffer;
+
+public class HadoopCodecCompressor
+        implements Compressor
+{
+    private final CompressionCodec codec;
+    private final Compressor blockCompressorForSizeCalculation;
+
+    public HadoopCodecCompressor(CompressionCodec codec, Compressor blockCompressorForSizeCalculation)
+    {
+        this.codec = codec;
+        this.blockCompressorForSizeCalculation = blockCompressorForSizeCalculation;
+    }
+
+    @Override
+    public int maxCompressedLength(int uncompressedSize)
+    {
+        // assume hadoop stream encoder won't increase size by more than 10% over the block encoder
+        return (int) ((blockCompressorForSizeCalculation.maxCompressedLength(uncompressedSize) * 1.1) + 8);
+    }
+
+    @Override
+    public int compress(byte[] input, int inputOffset, int inputLength, byte[] output, int outputOffset, int maxOutputLength)
+    {
+        ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream(output, outputOffset, maxOutputLength);
+
+        try {
+            OutputStream out = codec.createOutputStream(byteArrayOutputStream);
+            // write in a single shot to cause multiple chunks per block
+            out.write(input, inputOffset, inputLength);
+            out.close();
+        }
+        catch (IOException e) {
+            throw new UncheckedIOException(e);
+        }
+
+        return byteArrayOutputStream.size();
+    }
+
+    @Override
+    public void compress(ByteBuffer input, ByteBuffer output)
+    {
+        throw new UnsupportedOperationException("not yet implemented");
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecDecompressor.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecDecompressor.java
new file mode 100644
index 00000000000..5425fd8d4ff
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/HadoopCodecDecompressor.java
@@ -0,0 +1,65 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import org.apache.hadoop.io.compress.CompressionCodec;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.UncheckedIOException;
+import java.nio.ByteBuffer;
+
+public class HadoopCodecDecompressor
+        implements Decompressor
+{
+    private final CompressionCodec codec;
+
+    public HadoopCodecDecompressor(CompressionCodec codec)
+    {
+        this.codec = codec;
+    }
+
+    @Override
+    public int decompress(byte[] input, int inputOffset, int inputLength, byte[] output, int outputOffset, int maxOutputLength)
+            throws MalformedInputException
+    {
+        try (InputStream in = codec.createInputStream(new ByteArrayInputStream(input, inputOffset, inputLength))) {
+            int bytesRead = 0;
+            while (bytesRead < maxOutputLength) {
+                int size = in.read(output, outputOffset + bytesRead, maxOutputLength - bytesRead);
+                if (size < 0) {
+                    break;
+                }
+                bytesRead += size;
+            }
+
+            if (in.read() >= 0) {
+                throw new RuntimeException("All input was not consumed");
+            }
+
+            return bytesRead;
+        }
+        catch (IOException e) {
+            throw new UncheckedIOException(e);
+        }
+    }
+
+    @Override
+    public void decompress(ByteBuffer input, ByteBuffer output)
+            throws MalformedInputException
+    {
+        throw new UnsupportedOperationException("not yet implemented");
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/TestingModule.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/TestingModule.java
new file mode 100644
index 00000000000..d66c2672c3f
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/TestingModule.java
@@ -0,0 +1,55 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import com.google.inject.Binder;
+import com.google.inject.Module;
+import com.google.inject.Provides;
+import ai.vespa.airlift.compress.benchmark.DataSet;
+import org.openjdk.jmh.annotations.Param;
+
+import javax.inject.Singleton;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+public class TestingModule
+        implements Module
+{
+    @Override
+    public void configure(Binder binder)
+    {
+    }
+
+    @Provides
+    @Singleton
+    public List<DataSet> dataSets()
+            throws NoSuchFieldException, IOException
+    {
+        String[] testNames = DataSet.class
+                .getDeclaredField("name")
+                .getAnnotation(Param.class)
+                .value();
+
+        List<DataSet> result = new ArrayList<>();
+        for (String testName : testNames) {
+            DataSet entry = new DataSet(testName);
+            entry.loadFile();
+            result.add(entry);
+        }
+
+        return result;
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/Util.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/Util.java
new file mode 100644
index 00000000000..b4bc80557ee
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/Util.java
@@ -0,0 +1,41 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress;
+
+import static java.lang.String.format;
+
+public final class Util
+{
+    private Util()
+    {
+    }
+
+    public static String toHumanReadableSpeed(long bytesPerSecond)
+    {
+        String humanReadableSpeed;
+        if (bytesPerSecond < 1024 * 10L) {
+            humanReadableSpeed = format("%dB/s", bytesPerSecond);
+        }
+        else if (bytesPerSecond < 1024 * 1024 * 10L) {
+            humanReadableSpeed = format("%.1fkB/s", bytesPerSecond / 1024.0f);
+        }
+        else if (bytesPerSecond < 1024 * 1024 * 1024 * 10L) {
+            humanReadableSpeed = format("%.1fMB/s", bytesPerSecond / (1024.0f * 1024.0f));
+        }
+        else {
+            humanReadableSpeed = format("%.1fGB/s", bytesPerSecond / (1024.0f * 1024.0f * 1024.0f));
+        }
+        return humanReadableSpeed;
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/benchmark/DataSet.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/benchmark/DataSet.java
new file mode 100644
index 00000000000..5db909eaef8
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/benchmark/DataSet.java
@@ -0,0 +1,129 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress.benchmark;
+
+import com.google.common.io.Files;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+
+import java.io.File;
+import java.io.IOException;
+
+@State(Scope.Thread)
+public class DataSet
+{
+    @Param({
+            "canterbury/alice29.txt",
+            "canterbury/asyoulik.txt",
+            "canterbury/cp.html",
+            "canterbury/fields.c",
+            "canterbury/grammar.lsp",
+            "canterbury/kennedy.xls",
+            "canterbury/lcet10.txt",
+            "canterbury/plrabn12.txt",
+            "canterbury/ptt5",
+            "canterbury/sum",
+            "canterbury/xargs.1",
+
+            "silesia/dickens",
+            "silesia/mozilla",
+            "silesia/mr",
+            "silesia/nci",
+            "silesia/ooffice",
+            "silesia/osdb",
+            "silesia/reymont",
+            "silesia/samba",
+            "silesia/sao",
+            "silesia/webster",
+            "silesia/x-ray",
+            "silesia/xml",
+
+            "calgary/bib",
+            "calgary/book1",
+            "calgary/book2",
+            "calgary/geo",
+            "calgary/news",
+            "calgary/obj1",
+            "calgary/obj2",
+            "calgary/paper1",
+            "calgary/paper2",
+            "calgary/paper3",
+            "calgary/paper4",
+            "calgary/paper5",
+            "calgary/paper6",
+            "calgary/pic",
+            "calgary/progc",
+            "calgary/progl",
+            "calgary/progp",
+            "calgary/trans",
+
+            "artificial/a.txt",
+            "artificial/aaa.txt",
+            "artificial/alphabet.txt",
+            "artificial/random.txt",
+            "artificial/uniform_ascii.bin", // random ASCII with uniform probabilities per symbol
+
+            "large/bible.txt",
+            "large/E.coli",
+            "large/world192.txt",
+
+            "geo.protodata",
+            "house.jpg",
+            "html",
+            "kppkn.gtb",
+            "mapreduce-osdi-1.pdf",
+            "urls.10K",
+    })
+    private String name;
+    private byte[] uncompressed;
+
+    public DataSet()
+    {
+    }
+
+    public DataSet(String name)
+    {
+        this.name = name;
+    }
+
+    public DataSet(String name, byte[] uncompressed)
+    {
+        this.name = name;
+        this.uncompressed = uncompressed;
+    }
+
+    @Setup
+    public void loadFile()
+            throws IOException
+    {
+        uncompressed = Files.toByteArray(new File("testdata", name));
+    }
+
+    public byte[] getUncompressed()
+    {
+        return uncompressed;
+    }
+
+    public String getName()
+    {
+        return name;
+    }
+
+    public String toString()
+    {
+        return name;
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniCompressor.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniCompressor.java
new file mode 100644
index 00000000000..5874167150a
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniCompressor.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress.thirdparty;
+
+import com.github.luben.zstd.Zstd;
+import ai.vespa.airlift.compress.Compressor;
+
+import java.nio.ByteBuffer;
+
+public class ZstdJniCompressor
+        implements Compressor
+{
+    private final int level;
+
+    public ZstdJniCompressor(int level)
+    {
+        this.level = level;
+    }
+
+    @Override
+    public int maxCompressedLength(int uncompressedSize)
+    {
+        return (int) Zstd.compressBound(uncompressedSize);
+    }
+
+    @Override
+    public int compress(byte[] input, int inputOffset, int inputLength, byte[] output, int outputOffset, int maxOutputLength)
+    {
+        return (int) Zstd.compressByteArray(output, outputOffset, maxOutputLength, input, inputOffset, inputLength, level);
+    }
+
+    @Override
+    public void compress(ByteBuffer input, ByteBuffer output)
+    {
+        Zstd.compress(input, output, level);
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniDecompressor.java b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniDecompressor.java
new file mode 100644
index 00000000000..63e9de99f86
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/compress/thirdparty/ZstdJniDecompressor.java
@@ -0,0 +1,38 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.compress.thirdparty;
+
+import com.github.luben.zstd.Zstd;
+import ai.vespa.airlift.compress.Decompressor;
+import ai.vespa.airlift.compress.MalformedInputException;
+
+import java.nio.ByteBuffer;
+
+public class ZstdJniDecompressor
+        implements Decompressor
+{
+    @Override
+    public int decompress(byte[] input, int inputOffset, int inputLength, byte[] output, int outputOffset, int maxOutputLength)
+            throws MalformedInputException
+    {
+        return (int) Zstd.decompressByteArray(output, outputOffset, maxOutputLength, input, inputOffset, inputLength);
+    }
+
+    @Override
+    public void decompress(ByteBuffer input, ByteBuffer output)
+            throws MalformedInputException
+    {
+        Zstd.decompress(output, input);
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestCompressor.java b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestCompressor.java
new file mode 100644
index 00000000000..884ab8f2577
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestCompressor.java
@@ -0,0 +1,97 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.zstd;
+
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static sun.misc.Unsafe.ARRAY_BYTE_BASE_OFFSET;
+
+public class TestCompressor
+{
+    @Test
+    public void testMagic()
+    {
+        byte[] buffer = new byte[4];
+        int address = ARRAY_BYTE_BASE_OFFSET;
+
+        ZstdFrameCompressor.writeMagic(buffer, address, address + buffer.length);
+        ZstdFrameDecompressor.verifyMagic(buffer, address, address + buffer.length);
+    }
+
+    @Test(expectedExceptions = IllegalArgumentException.class, expectedExceptionsMessageRegExp = ".*buffer too small.*")
+    public void testMagicFailsWithSmallBuffer()
+    {
+        byte[] buffer = new byte[3];
+        ZstdFrameCompressor.writeMagic(buffer, ARRAY_BYTE_BASE_OFFSET, ARRAY_BYTE_BASE_OFFSET + buffer.length);
+    }
+
+    @Test(expectedExceptions = IllegalArgumentException.class, expectedExceptionsMessageRegExp = ".*buffer too small.*")
+    public void testFrameHeaderFailsWithSmallBuffer()
+    {
+        byte[] buffer = new byte[ZstdFrameCompressor.MAX_FRAME_HEADER_SIZE - 1];
+        ZstdFrameCompressor.writeFrameHeader(buffer, ARRAY_BYTE_BASE_OFFSET, ARRAY_BYTE_BASE_OFFSET + buffer.length, 1000, 1024);
+    }
+
+    @Test
+    public void testFrameHeader()
+    {
+        verifyFrameHeader(1, 1024, new FrameHeader(2, -1, 1, -1, true));
+        verifyFrameHeader(256, 1024, new FrameHeader(3, -1, 256, -1, true));
+
+        verifyFrameHeader(65536 + 256, 1024 + 128, new FrameHeader(6, 1152, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 2, new FrameHeader(6, 1024 + 128 * 2, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 3, new FrameHeader(6, 1024 + 128 * 3, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 4, new FrameHeader(6, 1024 + 128 * 4, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 5, new FrameHeader(6, 1024 + 128 * 5, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 6, new FrameHeader(6, 1024 + 128 * 6, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 7, new FrameHeader(6, 1024 + 128 * 7, 65536 + 256, -1, true));
+        verifyFrameHeader(65536 + 256, 1024 + 128 * 8, new FrameHeader(6, 1024 + 128 * 8, 65536 + 256, -1, true));
+
+        verifyFrameHeader(65536 + 256, 2048, new FrameHeader(6, 2048, 65536 + 256, -1, true));
+
+        verifyFrameHeader(Integer.MAX_VALUE, 1024, new FrameHeader(6, 1024, Integer.MAX_VALUE, -1, true));
+    }
+
+    @Test(expectedExceptions = IllegalArgumentException.class, expectedExceptionsMessageRegExp = "Minimum window size is 1024")
+    public void testMinimumWindowSize()
+    {
+        byte[] buffer = new byte[ZstdFrameCompressor.MAX_FRAME_HEADER_SIZE];
+        int address = ARRAY_BYTE_BASE_OFFSET;
+
+        ZstdFrameCompressor.writeFrameHeader(buffer, address, address + buffer.length, 2000, 1023);
+    }
+
+    @Test(expectedExceptions = IllegalArgumentException.class, expectedExceptionsMessageRegExp = "\\QWindow size of magnitude 2^10 must be multiple of 128\\E")
+    public void testWindowSizePrecision()
+    {
+        byte[] buffer = new byte[ZstdFrameCompressor.MAX_FRAME_HEADER_SIZE];
+        int address = ARRAY_BYTE_BASE_OFFSET;
+
+        ZstdFrameCompressor.writeFrameHeader(buffer, address, address + buffer.length, 2000, 1025);
+    }
+
+    private void verifyFrameHeader(int inputSize, int windowSize, FrameHeader expected)
+    {
+        byte[] buffer = new byte[ZstdFrameCompressor.MAX_FRAME_HEADER_SIZE];
+        int address = ARRAY_BYTE_BASE_OFFSET;
+
+        int size = ZstdFrameCompressor.writeFrameHeader(buffer, address, address + buffer.length, inputSize, windowSize);
+
+        assertEquals(size, expected.headerSize);
+
+        FrameHeader actual = ZstdFrameDecompressor.readFrameHeader(buffer, address, address + buffer.length);
+        assertEquals(actual, expected);
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestXxHash64.java b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestXxHash64.java
new file mode 100644
index 00000000000..b78888ca66e
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestXxHash64.java
@@ -0,0 +1,83 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.zstd;
+
+import net.jpountz.xxhash.XXHash64;
+import net.jpountz.xxhash.XXHashFactory;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static sun.misc.Unsafe.ARRAY_BYTE_BASE_OFFSET;
+
+// forked from https://github.com/airlift/slice
+public class TestXxHash64
+{
+    private static final long PRIME = 2654435761L;
+
+    private final byte[] buffer = new byte[101];
+
+    public TestXxHash64()
+    {
+        long value = PRIME;
+        for (int i = 0; i < buffer.length; i++) {
+            buffer[i] = (byte) (value >> 24);
+            value *= value;
+        }
+    }
+
+    @Test
+    public void testSanity()
+    {
+        assertHash(0, buffer, 0, 0xEF46DB3751D8E999L);
+
+        assertHash(0, buffer, 1, 0x4FCE394CC88952D8L);
+        assertHash(PRIME, buffer, 1, 0x739840CB819FA723L);
+
+        assertHash(0, buffer, 4, 0x9256E58AA397AEF1L);
+        assertHash(PRIME, buffer, 4, 0x9D5FFDFB928AB4BL);
+
+        assertHash(0, buffer, 8, 0xF74CB1451B32B8CFL);
+        assertHash(PRIME, buffer, 8, 0x9C44B77FBCC302C5L);
+
+        assertHash(0, buffer, 14, 0xCFFA8DB881BC3A3DL);
+        assertHash(PRIME, buffer, 14, 0x5B9611585EFCC9CBL);
+
+        assertHash(0, buffer, 32, 0xAF5753D39159EDEEL);
+        assertHash(PRIME, buffer, 32, 0xDCAB9233B8CA7B0FL);
+
+        assertHash(0, buffer, buffer.length, 0x0EAB543384F878ADL);
+        assertHash(PRIME, buffer, buffer.length, 0xCAA65939306F1E21L);
+    }
+
+    @Test
+    public void testMultipleLengths()
+    {
+        XXHash64 jpountz = XXHashFactory.fastestInstance().hash64();
+        for (int i = 0; i < 20_000; i++) {
+            byte[] data = new byte[i];
+            long expected = jpountz.hash(data, 0, data.length, 0);
+            assertHash(0, data, data.length, expected);
+        }
+    }
+
+    private static void assertHash(long seed, byte[] data, int length, long expected)
+    {
+        assertEquals(hash(seed, data, length), expected);
+    }
+
+    private static long hash(long seed, byte[] data, int length)
+    {
+        return XxHash64.hash(seed, data, ARRAY_BYTE_BASE_OFFSET, length);
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstd.java b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstd.java
new file mode 100644
index 00000000000..f947122ce6a
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstd.java
@@ -0,0 +1,201 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.zstd;
+
+import com.google.common.io.Resources;
+import ai.vespa.airlift.compress.AbstractTestCompression;
+import ai.vespa.airlift.compress.Compressor;
+import ai.vespa.airlift.compress.Decompressor;
+import ai.vespa.airlift.compress.MalformedInputException;
+import ai.vespa.airlift.compress.benchmark.DataSet;
+import ai.vespa.airlift.compress.thirdparty.ZstdJniCompressor;
+import ai.vespa.airlift.compress.thirdparty.ZstdJniDecompressor;
+import org.testng.annotations.Test;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+import static org.testng.Assert.assertEquals;
+
+public class TestZstd
+        extends AbstractTestCompression
+{
+    @Override
+    protected Compressor getCompressor()
+    {
+        return new ZstdCompressor();
+    }
+
+    @Override
+    protected Decompressor getDecompressor()
+    {
+        return new ZstdDecompressor();
+    }
+
+    @Override
+    protected Compressor getVerifyCompressor()
+    {
+        return new ZstdJniCompressor(3);
+    }
+
+    @Override
+    protected Decompressor getVerifyDecompressor()
+    {
+        return new ZstdJniDecompressor();
+    }
+
+    // Ideally, this should be covered by super.testDecompressWithOutputPadding(...), but the data written by the native
+    // compressor doesn't include checksums, so it's not a comprehensive test. The dataset for this test has a checksum.
+    @Test
+    public void testDecompressWithOutputPaddingAndChecksum()
+            throws IOException
+    {
+        int padding = 1021;
+
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/with-checksum.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/with-checksum"));
+
+        byte[] output = new byte[uncompressed.length + padding * 2]; // pre + post padding
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressed.length, output, padding, output.length - padding);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressed.length, output, padding, decompressedSize);
+    }
+
+    @Test
+    public void testConcatenatedFrames()
+            throws IOException
+    {
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames"));
+
+        byte[] output = new byte[uncompressed.length];
+        getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressed.length, output, 0, output.length);
+    }
+
+    @Test
+    public void testInvalidSequenceOffset()
+            throws IOException
+    {
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/offset-before-start.zst"));
+        byte[] output = new byte[compressed.length * 10];
+
+        assertThatThrownBy(() -> getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length))
+                .isInstanceOf(MalformedInputException.class)
+                .hasMessageStartingWith("Input is corrupted: offset=894");
+    }
+
+    @Test
+    public void testSmallLiteralsAfterIncompressibleLiterals()
+            throws IOException
+    {
+        // Ensure the compressor doesn't try to reuse a huffman table that was created speculatively for a previous block
+        // which ended up emitting raw literals due to insufficient gain
+        Compressor compressor = getCompressor();
+
+        byte[] original = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/small-literals-after-incompressible-literals"));
+        int maxCompressLength = compressor.maxCompressedLength(original.length);
+
+        byte[] compressed = new byte[maxCompressLength];
+        int compressedSize = compressor.compress(original, 0, original.length, compressed, 0, compressed.length);
+
+        byte[] decompressed = new byte[original.length];
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressedSize, decompressed, 0, decompressed.length);
+
+        assertByteArraysEqual(original, 0, original.length, decompressed, 0, decompressedSize);
+    }
+
+    @Test
+    public void testLargeRle()
+            throws IOException
+    {
+        // Dataset that produces an RLE block with 3-byte header
+
+        Compressor compressor = getCompressor();
+
+        byte[] original = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/large-rle"));
+        int maxCompressLength = compressor.maxCompressedLength(original.length);
+
+        byte[] compressed = new byte[maxCompressLength];
+        int compressedSize = compressor.compress(original, 0, original.length, compressed, 0, compressed.length);
+
+        byte[] decompressed = new byte[original.length];
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressedSize, decompressed, 0, decompressed.length);
+
+        assertByteArraysEqual(original, 0, original.length, decompressed, 0, decompressedSize);
+    }
+
+    @Test
+    public void testIncompressibleData()
+            throws IOException
+    {
+        // Incompressible data that would require more than maxCompressedLength(...) to store
+
+        Compressor compressor = getCompressor();
+
+        byte[] original = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/incompressible"));
+        int maxCompressLength = compressor.maxCompressedLength(original.length);
+
+        byte[] compressed = new byte[maxCompressLength];
+        int compressedSize = compressor.compress(original, 0, original.length, compressed, 0, compressed.length);
+
+        byte[] decompressed = new byte[original.length];
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressedSize, decompressed, 0, decompressed.length);
+
+        assertByteArraysEqual(original, 0, original.length, decompressed, 0, decompressedSize);
+    }
+
+    @Test
+    public void testMaxCompressedSize()
+    {
+        assertEquals(new ZstdCompressor().maxCompressedLength(0), 64);
+        assertEquals(new ZstdCompressor().maxCompressedLength(64 * 1024), 65_824);
+        assertEquals(new ZstdCompressor().maxCompressedLength(128 * 1024), 131_584);
+        assertEquals(new ZstdCompressor().maxCompressedLength(128 * 1024 + 1), 131_585);
+    }
+
+    // test over data sets, should the result depend on input size or its compressibility
+    @Test(dataProvider = "data")
+    public void testGetDecompressedSize(DataSet dataSet)
+    {
+        Compressor compressor = getCompressor();
+        byte[] originalUncompressed = dataSet.getUncompressed();
+        byte[] compressed = new byte[compressor.maxCompressedLength(originalUncompressed.length)];
+
+        int compressedLength = compressor.compress(originalUncompressed, 0, originalUncompressed.length, compressed, 0, compressed.length);
+
+        assertEquals(ZstdDecompressor.getDecompressedSize(compressed, 0, compressedLength), originalUncompressed.length);
+
+        int padding = 10;
+        byte[] compressedWithPadding = new byte[compressedLength + padding];
+        Arrays.fill(compressedWithPadding, (byte) 42);
+        System.arraycopy(compressed, 0, compressedWithPadding, padding, compressedLength);
+        assertEquals(ZstdDecompressor.getDecompressedSize(compressedWithPadding, padding, compressedLength), originalUncompressed.length);
+    }
+
+    @Test
+    public void testVerifyMagicInAllFrames()
+            throws IOException
+    {
+        Compressor compressor = getCompressor();
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/bad-second-frame.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames"));
+        byte[] output = new byte[uncompressed.length];
+        assertThatThrownBy(() -> getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length))
+                .isInstanceOf(MalformedInputException.class)
+                .hasMessageStartingWith("Invalid magic prefix");
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstdInputStream.java b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstdInputStream.java
new file mode 100644
index 00000000000..b983389f2ef
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/TestZstdInputStream.java
@@ -0,0 +1,242 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.zstd;
+
+import com.google.common.io.Resources;
+import ai.vespa.airlift.compress.AbstractTestCompression;
+import ai.vespa.airlift.compress.Compressor;
+import ai.vespa.airlift.compress.Decompressor;
+import ai.vespa.airlift.compress.MalformedInputException;
+import ai.vespa.airlift.compress.thirdparty.ZstdJniCompressor;
+import ai.vespa.airlift.compress.thirdparty.ZstdJniDecompressor;
+import org.testng.annotations.Test;
+
+import java.io.ByteArrayInputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.nio.ByteBuffer;
+
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+public class TestZstdInputStream
+        extends AbstractTestCompression
+{
+    static class ByteBufferBackedInputStream
+            extends InputStream
+    {
+        ByteBuffer buf;
+
+        public ByteBufferBackedInputStream(ByteBuffer buf)
+        {
+            this.buf = buf;
+        }
+
+        public int read()
+        {
+            if (!buf.hasRemaining()) {
+                return -1;
+            }
+            return buf.get() & 0xFF;
+        }
+
+        public int read(byte[] bytes, int off, int len)
+        {
+            if (!buf.hasRemaining()) {
+                return -1;
+            }
+            len = Math.min(len, buf.remaining());
+            if (buf.position() < 1) {
+                len = 1;
+            }
+            buf.get(bytes, off, len);
+            return len;
+        }
+    }
+
+    static class WrapDecompressor
+            implements Decompressor
+    {
+        public int decompress(byte[] input, int inputOffset, int inputLength, byte[] output, int outputOffset, int maxOutputLength)
+                throws MalformedInputException
+        {
+            verifyRange(input, inputOffset, inputLength);
+            verifyRange(output, outputOffset, maxOutputLength);
+            try {
+                int res = 0;
+                ByteArrayInputStream ba = new ByteArrayInputStream(input, inputOffset, inputLength);
+                InputStream zin = new ZstdInputStream(ba);
+                while (res < maxOutputLength) {
+                    int len = zin.read(output, outputOffset, maxOutputLength - res);
+                    if (len == -1) {
+                        return res;
+                    }
+                    res += len;
+                    outputOffset += len;
+                }
+                if (zin.read() != -1) {
+                    throw new RuntimeException("All input was not consumed");
+                }
+                return res;
+            }
+            catch (IOException e) {
+                throw new RuntimeException("bad io", e);
+            }
+        }
+
+        public void decompress(ByteBuffer input, ByteBuffer output)
+                throws MalformedInputException
+        {
+            try {
+                byte[] tmp = new byte[output.remaining()];
+                ByteBufferBackedInputStream bb = new ByteBufferBackedInputStream(input);
+                InputStream zin = new ZstdInputStream(bb);
+                while (output.position() < output.limit()) {
+                    int len = zin.read(tmp);
+                    if (len == -1) {
+                        return;
+                    }
+                    output.put(tmp, 0, len);
+                }
+            }
+            catch (IOException ignored) {
+            }
+        }
+
+        private static void verifyRange(byte[] data, int offset, int length)
+        {
+            if (offset < 0 || length < 0 || offset + length > data.length) {
+                throw new IllegalArgumentException("Invalid offset or length");
+            }
+        }
+    }
+
+    @Override
+    protected Compressor getCompressor()
+    {
+        return new ZstdCompressor();
+    }
+
+    @Override
+    protected Decompressor getDecompressor()
+    {
+        return new WrapDecompressor();
+    }
+
+    @Override
+    protected Compressor getVerifyCompressor()
+    {
+        return new ZstdJniCompressor(3);
+    }
+
+    @Override
+    protected Decompressor getVerifyDecompressor()
+    {
+        return new ZstdJniDecompressor();
+    }
+
+    // Ideally, this should be covered by super.testDecompressWithOutputPadding(...), but the data written by the native
+    // compressor doesn't include checksums, so it's not a comprehensive test. The dataset for this test has a checksum.
+    @Test
+    public void testDecompressWithOutputPaddingAndChecksum()
+            throws IOException
+    {
+        int padding = 1021;
+
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/with-checksum.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/with-checksum"));
+
+        byte[] output = new byte[uncompressed.length + padding * 2]; // pre + post padding
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressed.length, output, padding, output.length - padding);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressed.length, output, padding, decompressedSize);
+    }
+
+    @Test
+    public void testConcatenatedFrames()
+            throws IOException
+    {
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames"));
+
+        byte[] output = new byte[uncompressed.length];
+        getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length);
+
+        assertByteArraysEqual(uncompressed, 0, uncompressed.length, output, 0, output.length);
+    }
+
+    @Test
+    public void testInvalidSequenceOffset()
+            throws IOException
+    {
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/offset-before-start.zst"));
+        byte[] output = new byte[compressed.length * 10];
+
+        assertThatThrownBy(() -> getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length))
+                .isInstanceOf(MalformedInputException.class)
+                .hasMessageStartingWith("Input is corrupted: offset=894");
+    }
+
+    @Test
+    public void testLargeRle()
+            throws IOException
+    {
+        // Dataset that produces an RLE block with 3-byte header
+
+        Compressor compressor = getCompressor();
+
+        byte[] original = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/large-rle"));
+        int maxCompressLength = compressor.maxCompressedLength(original.length);
+
+        byte[] compressed = new byte[maxCompressLength];
+        int compressedSize = compressor.compress(original, 0, original.length, compressed, 0, compressed.length);
+
+        byte[] decompressed = new byte[original.length];
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressedSize, decompressed, 0, decompressed.length);
+
+        assertByteArraysEqual(original, 0, original.length, decompressed, 0, decompressedSize);
+    }
+
+    @Test
+    public void testIncompressibleData()
+            throws IOException
+    {
+        // Incompressible data that would require more than maxCompressedLength(...) to store
+
+        Compressor compressor = getCompressor();
+
+        byte[] original = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/incompressible"));
+        int maxCompressLength = compressor.maxCompressedLength(original.length);
+
+        byte[] compressed = new byte[maxCompressLength];
+        int compressedSize = compressor.compress(original, 0, original.length, compressed, 0, compressed.length);
+
+        byte[] decompressed = new byte[original.length];
+        int decompressedSize = getDecompressor().decompress(compressed, 0, compressedSize, decompressed, 0, decompressed.length);
+
+        assertByteArraysEqual(original, 0, original.length, decompressed, 0, decompressedSize);
+    }
+
+    @Test
+    public void testVerifyMagicInAllFrames()
+            throws IOException
+    {
+        Compressor compressor = getCompressor();
+        byte[] compressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/bad-second-frame.zst"));
+        byte[] uncompressed = Resources.toByteArray(getClass().getClassLoader().getResource("data/zstd/multiple-frames"));
+        byte[] output = new byte[uncompressed.length];
+        assertThatThrownBy(() -> getDecompressor().decompress(compressed, 0, compressed.length, output, 0, output.length))
+                .isInstanceOf(MalformedInputException.class)
+                .hasMessageStartingWith("Invalid magic prefix");
+    }
+}
diff --git a/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/ZstdCat.java b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/ZstdCat.java
new file mode 100644
index 00000000000..6fc1a223a6e
--- /dev/null
+++ b/airlift-zstd/src/test/java/ai/vespa/airlift/zstd/ZstdCat.java
@@ -0,0 +1,44 @@
+/*
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package ai.vespa.airlift.zstd;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+/*
+ * Simple test implementation of "zstdcat".
+ * @author arnej27959
+ */
+public class ZstdCat
+{
+    private ZstdCat() {}
+
+    public static void main(String[] args)
+    {
+        try {
+            InputStream i = new ZstdInputStream(System.in);
+            byte[] buf = new byte[100 * 1024];
+            int rl = 0;
+            do {
+                rl = i.read(buf);
+                if (rl > 0) {
+                    System.out.write(buf, 0, rl);
+                }
+            } while (rl > 0);
+        }
+        catch (IOException e) {
+            System.err.println("IO failed" + e);
+        }
+    }
+}
diff --git a/airlift-zstd/src/test/resources/data/zstd/bad-second-frame.zst b/airlift-zstd/src/test/resources/data/zstd/bad-second-frame.zst
new file mode 100644
index 00000000000..a98549e580d
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/bad-second-frame.zst
diff --git a/airlift-zstd/src/test/resources/data/zstd/incompressible b/airlift-zstd/src/test/resources/data/zstd/incompressible
new file mode 100644
index 00000000000..f1567c4067e
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/incompressible
diff --git a/airlift-zstd/src/test/resources/data/zstd/large-rle b/airlift-zstd/src/test/resources/data/zstd/large-rle
new file mode 100644
index 00000000000..8591058e5f4
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/large-rle
@@ -0,0 +1 @@
+01234299995678929999101112131429999151617181929999202122232429999252627282929999303132333429999353637383929999404142434429999454647484929999505152535429999555657585929999606162636429999656667686929999707172737429999757677787929999808182838429999858687888929999909192939429999959697989929999100101102103104299991051061071081092999911011111211311429999115116117118119299991201211221231242999912512612712812929999130131132133134299991351361371381392999914014114214314429999145146147148149299991501511521531542999915515615715815929999160161162163164299991651661671681692999917017117217317429999175176177178179299991801811821831842999918518618718818929999190191192193194299991951961971981992999920020120220320429999205206207208209299992102112122132142999921521621721821929999220221222223224299992252262272282292999923023123223323429999235236237238239299992402412422432442999924524624724824929999250251252253254299992552562572582592999926026126226326429999265266267268269299992702712722732742999927527627727827929999280281282283284299992852862872882892999929029129229329429999295296297298299299993003013023033042999930530630730830929999310311312313314299993153163173183192999932032132232332429999325326327328329299993303313323333342999933533633733833929999340341342343344299993453463473483492999935035135235335429999355356357358359299993603613623633642999936536636736836929999370371372373374299993753763773783792999938038138238338429999385386387388389299993903913923933942999939539639739839929999400401402403404299994054064074084092999941041141241341429999415416417418419299994204214224234242999942542642742842929999430431432433434299994354364374384392999944044144244344429999445446447448449299994504514524534542999945545645745845929999460461462463464299994654664674684692999947047147247347429999475476477478479299994804814824834842999948548648748848929999490491492493494299994954964974984992999950050150250350429999505506507508509299995105115125135142999951551651751851929999520521522523524299995255265275285292999953053153253353429999535536537538539299995405415425435442999954554654754854929999550551552553554299995555565575585592999956056156256356429999565566567568569299995705715725735742999957557657757857929999580581582583584299995855865875885892999959059159259359429999595596597598599299996006016026036042999960560660760860929999610611612613614299996156166176186192999962062162262362429999625626627628629299996306316326336342999963563663763863929999640641642643644299996456466476486492999965065165265365429999655656657658659299996606616626636642999966566666766866929999670671672673674299996756766776786792999968068168268368429999685686687688689299996906916926936942999969569669769869929999700701702703704299997057067077087092999971071171271371429999715716717718719299997207217227237242999972572672772872929999730731732733734299997357367377387392999974074174274374429999745746747748749299997507517527537542999975575675775875929999760761762763764299997657667677687692999977077177277377429999775776777778779299997807817827837842999978578678778878929999790791792793794299997957967977987992999980080180280380429999805806807808809299998108118128138142999981581681781881929999820821822823824299998258268278288292999983083183283383429999835836837838839299998408418428438442999984584684784884929999850851852853854299998558568578588592999986086186286386429999865866867868869299998708718728738742999987587687787887929999880881882883884299998858868878888892999989089189289389429999895896897898899299999009019029039042999990590690790890929999910911912913914299999159169179189192999992092192292392429999925926927928929299999309319329339342999993593693793893929999940941942943944299999459469479489492999995095195295395429999955956957958959299999609619629639642999996596696796896929999970971972973974299999759769779789792999998098198298398429999985986987988989299999909919929939942999999599699799899929999100010011002100310042999910051006100710081009299991010101110121013101429999101510161017101810192999910201021102210231024299991025102610271028102929999103010311032103310342999910351036103710381039299991040104110421043104429999104510461047104810492999910501051105210531054299991055105610571058105929999106010611062106310642999910651066106710681069299991070107110721073107429999107510761077107810792999910801081108210831084299991085108610871088108929999109010911092109310942999910951096109710981099299991100110111021103110429999110511061107110811092999911101111111211131114299991115111611171118111929999112011211122112311242999911251126112711281129299991130113111321133113429999113511361137113811392999911401141114211431144299991145114611471148114929999115011511152115311542999911551156115711581159299991160116111621163116429999116511661167116811692999911701171117211731174299991175117611771178117929999118011811182118311842999911851186118711881189299991190119111921193119429999119511961197119811992999912001201120212031204299991205120612071208120929999121012111212121312142999912151216121712181219299991220122112221223122429999122512261227122812292999912301231123212331234299991235123612371238123929999124012411242124312442999912451246124712481249299991250125112521253125429999125512561257125812592999912601261126212631264299991265126612671268126929999127012711272127312742999912751276127712781279299991280128112821283128429999128512861287128812892999912901291129212931294299991295129612971298129929999130013011302130313042999913051306130713081309299991310131113121313131429999131513161317131813192999913201321132213231324299991325132613271328132929999133013311332133313342999913351336133713381339299991340134113421343134429999134513461347134813492999913501351135213531354299991355135613571358135929999136013611362136313642999913651366136713681369299991370137113721373137429999137513761377137813792999913801381138213831384299991385138613871388138929999139013911392139313942999913951396139713981399299991400140114021403140429999140514061407140814092999914101411141214131414299991415141614171418141929999142014211422142314242999914251426142714281429299991430143114321433143429999143514361437143814392999914401441144214431444299991445144614471448144929999145014511452145314542999914551456145714581459299991460146114621463146429999146514661467146814692999914701471147214731474299991475147614771478147929999148014811482148314842999914851486148714881489299991490149114921493149429999149514961497149814992999915001501150215031504299991505150615071508150929999151015111512151315142999915151516151715181519299991520152115221523152429999152515261527152815292999915301531153215331534299991535153615371538153929999154015411542154315442999915451546154715481549299991550155115521553155429999155515561557155815592999915601561156215631564299991565156615671568156929999157015711572157315742999915751576157715781579299991580158115821583158429999158515861587158815892999915901591159215931594299991595159615971598159929999160016011602160316042999916051606160716081609299991610161116121613161429999161516161617161816192999916201621162216231624299991625162616271628162929999163016311632163316342999916351636163716381639299991640164116421643164429999164516461647164816492999916501651165216531654299991655165616571658165929999166016611662166316642999916651666166716681669299991670167116721673167429999167516761677167816792999916801681168216831684299991685168616871688168929999169016911692169316942999916951696169716981699299991700170117021703170429999170517061707170817092999917101711171217131714299991715171617171718171929999172017211722172317242999917251726172717281729299991730173117321733173429999173517361737173817392999917401741174217431744299991745174617471748174929999175017511752175317542999917551756175717581759299991760176117621763176429999176517661767176817692999917701771177217731774299991775177617771778177929999178017811782178317842999917851786178717881789299991790179117921793179429999179517961797179817992999918001801180218031804299991805180618071808180929999181018111812181318142999918151816181718181819299991820182118221823182429999182518261827182818292999918301831183218331834299991835183618371838183929999184018411842184318442999918451846184718481849299991850185118521853185429999185518561857185818592999918601861186218631864299991865186618671868186929999187018711872187318742999918751876187718781879299991880188118821883188429999188518861887188818892999918901891189218931894299991895189618971898189929999190019011902190319042999919051906190719081909299991910191119121913191429999191519161917191819192999919201921192219231924299991925192619271928192929999193019311932193319342999919351936193719381939299991940194119421943194429999194519461947194819492999919501951195219531954299991955195619571958195929999196019611962196319642999919651966196719681969299991970197119721973197429999197519761977197819792999919801981198219831984299991985198619871988198929999199019911992199319942999919951996199719981999299992000200120022003200429999200520062007200820092999920102011201220132014299992015201620172018201929999202020212022202320242999920252026202720282029299992030203120322033203429999203520362037203820392999920402041204220432044299992045204620472048204929999205020512052205320542999920552056205720582059299992060206120622063206429999206520662067206820692999920702071207220732074299992075207620772078207929999208020812082208320842999920852086208720882089299992090209120922093209429999209520962097209820992999921002101210221032104299992105210621072108210929999211021112112211321142999921152116211721182119299992120212121222123212429999212521262127212821292999921302131213221332134299992135213621372138213929999214021412142214321442999921452146214721482149299992150215121522153215429999215521562157215821592999921602161216221632164299992165216621672168216929999217021712172217321742999921752176217721782179299992180218121822183218429999218521862187218821892999921902191219221932194299992195219621972198219929999220022012202220322042999922052206220722082209299992210221122122213221429999221522162217221822192999922202221222222232224299992225222622272228222929999223022312232223322342999922352236223722382239299992240224122422243224429999224522462247224822492999922502251225222532254299992255225622572258225929999226022612262226322642999922652266226722682269299992270227122722273227429999227522762277227822792999922802281228222832284299992285228622872288228929999229022912292229322942999922952296229722982299299992300230123022303230429999230523062307230823092999923102311231223132314299992315231623172318231929999232023212322232323242999923252326232723282329299992330233123322333233429999233523362337233823392999923402341234223432344299992345234623472348234929999235023512352235323542999923552356235723582359299992360236123622363236429999236523662367236823692999923702371237223732374299992375237623772378237929999238023812382238323842999923852386238723882389299992390239123922393239429999239523962397239823992999924002401240224032404299992405240624072408240929999241024112412241324142999924152416241724182419299992420242124222423242429999242524262427242824292999924302431243224332434299992435243624372438243929999244024412442244324442999924452446244724482449299992450245124522453245429999245524562457245824592999924602461246224632464299992465246624672468246929999247024712472247324742999924752476247724782479299992480248124822483248429999248524862487248824892999924902491249224932494299992495249624972498249929999250025012502250325042999925052506250725082509299992510251125122513251429999251525162517251825192999925202521252225232524299992525252625272528252929999253025312532253325342999925352536253725382539299992540254125422543254429999254525462547254825492999925502551255225532554299992555255625572558255929999256025612562256325642999925652566256725682569299992570257125722573257429999257525762577257825792999925802581258225832584299992585258625872588258929999259025912592259325942999925952596259725982599299992600260126022603260429999260526062607260826092999926102611261226132614299992615261626172618261929999262026212622262326242999926252626262726282629299992630263126322633263429999263526362637263826392999926402641264226432644299992645264626472648264929999265026512652265326542999926552656265726582659299992660266126622663266429999266526662667266826692999926702671267226732674299992675267626772678267929999268026812682268326842999926852686268726882689299992690269126922693269429999269526962697269826992999927002701270227032704299992705270627072708270929999271027112712271327142999927152716271727182719299992720272127222723272429999272527262727272827292999927302731273227332734299992735273627372738273929999274027412742274327442999927452746274727482749299992750275127522753275429999275527562757275827592999927602761276227632764299992765276627672768276929999277027712772277327742999927752776277727782779299992780278127822783278429999278527862787278827892999927902791279227932794299992795279627972798279929999280028012802280328042999928052806280728082809299992810281128122813281429999281528162817281828192999928202821282228232824299992825282628272828282929999283028312832283328342999928352836283728382839299992840284128422843284429999284528462847284828492999928502851285228532854299992855285628572858285929999286028612862286328642999928652866286728682869299992870287128722873287429999287528762877287828792999928802881288228832884299992885288628872888288929999289028912892289328942999928952896289728982899299992900290129022903290429999290529062907290829092999929102911291229132914299992915291629172918291929999292029212922292329242999929252926292729282929299992930293129322933293429999293529362937293829392999929402941294229432944299992945294629472948294929999295029512952295329542999929552956295729582959299992960296129622963296429999296529662967296829692999929702971297229732974299992975297629772978297929999298029812982298329842999929852986298729882989299992990299129922993299429999299529962997299829992999930003001300230033004299993005300630073008300929999301030113012301330142999930153016301730183019299993020302130223023302429999302530263027302830292999930303031303230333034299993035303630373038303929999304030413042304330442999930453046304730483049299993050305130523053305429999305530563057305830592999930603061306230633064299993065306630673068306929999307030713072307330742999930753076307730783079299993080308130823083308429999308530863087308830892999930903091309230933094299993095309630973098309929999310031013102310331042999931053106310731083109299993110311131123113311429999311531163117311831192999931203121312231233124299993125312631273128312929999313031313132313331342999931353136313731383139299993140314131423143314429999314531463147314831492999931503151315231533154299993155315631573158315929999316031613162316331642999931653166316731683169299993170317131723173317429999317531763177317831792999931803181318231833184299993185318631873188318929999319031913192319331942999931953196319731983199299993200320132023203320429999320532063207320832092999932103211321232133214299993215321632173218321929999322032213222322332242999932253226322732283229299993230323132323233323429999323532363237323832392999932403241324232433244299993245324632473248324929999325032513252325332542999932553256325732583259299993260326132623263326429999326532663267326832692999932703271327232733274299993275327632773278327929999328032813282328332842999932853286328732883289299993290329132923293329429999329532963297329832992999933003301330233033304299993305330633073308330929999331033113312331333142999933153316331733183319299993320332133223323332429999332533263327332833292999933303331333233333334299993335333633373338333929999334033413342334333442999933453346334733483349299993350335133523353335429999335533563357335833592999933603361336233633364299993365336633673368336929999337033713372337333742999933753376337733783379299993380338133823383338429999338533863387338833892999933903391339233933394299993395339633973398339929999340034013402340334042999934053406340734083409299993410341134123413341429999341534163417341834192999934203421342234233424299993425342634273428342929999343034313432343334342999934353436343734383439299993440344134423443344429999344534463447344834492999934503451345234533454299993455345634573458345929999346034613462346334642999934653466346734683469299993470347134723473347429999347534763477347834792999934803481348234833484299993485348634873488348929999349034913492349334942999934953496349734983499299993500350135023503350429999350535063507350835092999935103511351235133514299993515351635173518351929999352035213522352335242999935253526352735283529299993530353135323533353429999353535363537353835392999935403541354235433544299993545354635473548354929999355035513552355335542999935553556355735583559299993560356135623563356429999356535663567356835692999935703571357235733574299993575357635773578357929999358035813582358335842999935853586358735883589299993590359135923593359429999359535963597359835992999936003601360236033604299993605360636073608360929999361036113612361336142999936153616361736183619299993620362136223623362429999362536263627362836292999936303631363236333634299993635363636373638363929999364036413642364336442999936453646364736483649299993650365136523653365429999365536563657365836592999936603661366236633664299993665366636673668366929999367036713672367336742999936753676367736783679299993680368136823683368429999368536863687368836892999936903691369236933694299993695369636973698369929999370037013702370337042999937053706370737083709299993710371137123713371429999371537163717371837192999937203721372237233724299993725372637273728372929999373037313732373337342999937353736373737383739299993740374137423743374429999374537463747374837492999937503751375237533754299993755375637573758375929999376037613762376337642999937653766376737683769299993770377137723773377429999377537763777377837792999937803781378237833784299993785378637873788378929999379037913792379337942999937953796379737983799299993800380138023803380429999380538063807380838092999938103811381238133814299993815381638173818381929999382038213822382338242999938253826382738283829299993830383138323833383429999383538363837383838392999938403841384238433844299993845384638473848384929999385038513852385338542999938553856385738583859299993860386138623863386429999386538663867386838692999938703871387238733874299993875387638773878387929999388038813882388338842999938853886388738883889299993890389138923893389429999389538963897389838992999939003901390239033904299993905390639073908390929999391039113912391339142999939153916391739183919299993920392139223923392429999392539263927392839292999939303931393239333934299993935393639373938393929999394039413942394339442999939453946394739483949299993950395139523953395429999395539563957395839592999939603961396239633964299993965396639673968396929999397039713972397339742999939753976397739783979299993980398139823983398429999398539863987398839892999939903991399239933994299993995399639973998399929999400040014002400340042999940054006400740084009299994010401140124013401429999401540164017401840192999940204021402240234024299994025402640274028402929999403040314032403340342999940354036403740384039299994040404140424043404429999404540464047404840492999940504051405240534054299994055405640574058405929999406040614062406340642999940654066406740684069299994070407140724073407429999407540764077407840792999940804081408240834084299994085408640874088408929999409040914092409340942999940954096409740984099299994100410141024103410429999410541064107410841092999941104111411241134114299994115411641174118411929999412041214122412341242999941254126412741284129299994130413141324133413429999413541364137413841392999941404141414241434144299994145414641474148414929999415041514152415341542999941554156415741584159299994160416141624163416429999416541664167416841692999941704171417241734174299994175417641774178417929999418041814182418341842999941854186418741884189299994190419141924193419429999419541964197419841992999942004201420242034204299994205420642074208420929999421042114212421342142999942154216421742184219299994220422142224223422429999422542264227422842292999942304231423242334234299994235423642374238423929999424042414242424342442999942454246424742484249299994250425142524253425429999425542564257425842592999942604261426242634264299994265426642674268426929999427042714272427342742999942754276427742784279299994280428142824283428429999428542864287428842892999942904291429242934294299994295429642974298429929999430043014302430343042999943054306430743084309299994310431143124313431429999431543164317431843192999943204321432243234324299994325432643274328432929999433043314332433343342999943354336433743384339299994340434143424343434429999434543464347434843492999943504351435243534354299994355435643574358435929999436043614362436343642999943654366436743684369299994370437143724373437429999437543764377437843792999943804381438243834384299994385438643874388438929999439043914392439343942999943954396439743984399299994400440144024403440429999440544064407440844092999944104411441244134414299994415441644174418441929999442044214422442344242999944254426442744284429299994430443144324433443429999443544364437443844392999944404441444244434444299994445444644474448444929999445044514452445344542999944554456445744584459299994460446144624463446429999446544664467446844692999944704471447244734474299994475447644774478447929999448044814482448344842999944854486448744884489299994490449144924493449429999449544964497449844992999945004501450245034504299994505450645074508450929999451045114512451345142999945154516451745184519299994520452145224523452429999452545264527452845292999945304531453245334534299994535453645374538453929999454045414542454345442999945454546454745484549299994550455145524553455429999455545564557455845592999945604561456245634564299994565456645674568456929999457045714572457345742999945754576457745784579299994580458145824583458429999458545864587458845892999945904591459245934594299994595459645974598459929999460046014602460346042999946054606460746084609299994610461146124613461429999461546164617461846192999946204621462246234624299994625462646274628462929999463046314632463346342999946354636463746384639299994640464146424643464429999464546464647464846492999946504651465246534654299994655465646574658465929999466046614662466346642999946654666466746684669299994670467146724673467429999467546764677467846792999946804681468246834684299994685468646874688468929999469046914692469346942999946954696469746984699299994700470147024703470429999470547064707470847092999947104711471247134714299994715471647174718471929999472047214722472347242999947254726472747284729299994730473147324733473429999473547364737473847392999947404741474247434744299994745474647474748474929999475047514752475347542999947554756475747584759299994760476147624763476429999476547664767476847692999947704771477247734774299994775477647774778477929999478047814782478347842999947854786478747884789299994790479147924793479429999479547964797479847992999948004801480248034804299994805480648074808480929999481048114812481348142999948154816481748184819299994820482148224823482429999482548264827482848292999948304831483248334834299994835483648374838483929999484048414842484348442999948454846484748484849299994850485148524853485429999485548564857485848592999948604861486248634864299994865486648674868486929999487048714872487348742999948754876487748784879299994880488148824883488429999488548864887488848892999948904891489248934894299994895489648974898489929999490049014902490349042999949054906490749084909299994910491149124913491429999491549164917491849192999949204921492249234924299994925492649274928492929999493049314932493349342999949354936493749384939299994940494149424943494429999494549464947494849492999949504951495249534954299994955495649574958495929999496049614962496349642999949654966496749684969299994970497149724973497429999497549764977497849792999949804981498249834984299994985498649874988498929999499049914992499349942999949954996499749984999299995000500150025003500429999500550065007500850092999950105011501250135014299995015501650175018501929999502050215022502350242999950255026502750285029299995030503150325033503429999503550365037503850392999950405041504250435044299995045504650475048504929999505050515052505350542999950555056505750585059299995060506150625063506429999506550665067506850692999950705071507250735074299995075507650775078507929999508050815082508350842999950855086508750885089299995090509150925093509429999509550965097509850992999951005101510251035104299995105510651075108510929999511051115112511351142999951155116511751185119299995120512151225123512429999512551265127512851292999951305131513251335134299995135513651375138513929999514051415142514351442999951455146514751485149299995150515151525153515429999515551565157515851592999951605161516251635164299995165516651675168516929999517051715172517351742999951755176517751785179299995180518151825183518429999518551865187518851892999951905191519251935194299995195519651975198519929999520052015202520352042999952055206520752085209299995210521152125213521429999521552165217521852192999952205221522252235224299995225522652275228522929999523052315232523352342999952355236523752385239299995240524152425243524429999524552465247524852492999952505251525252535254299995255525652575258525929999526052615262526352642999952655266526752685269299995270527152725273527429999527552765277527852792999952805281528252835284299995285528652875288528929999529052915292529352942999952955296529752985299299995300530153025303530429999530553065307530853092999953105311531253135314299995315531653175318531929999532053215322532353242999953255326532753285329299995330533153325333533429999533553365337533853392999953405341534253435344299995345534653475348534929999535053515352535353542999953555356535753585359299995360536153625363536429999536553665367536853692999953705371537253735374299995375537653775378537929999538053815382538353842999953855386538753885389299995390539153925393539429999539553965397539853992999954005401540254035404299995405540654075408540929999541054115412541354142999954155416541754185419299995420542154225423542429999542554265427542854292999954305431543254335434299995435543654375438543929999544054415442544354442999954455446544754485449299995450545154525453545429999545554565457545854592999954605461546254635464299995465546654675468546929999547054715472547354742999954755476547754785479299995480548154825483548429999548554865487548854892999954905491549254935494299995495549654975498549929999550055015502550355042999955055506550755085509299995510551155125513551429999551555165517551855192999955205521552255235524299995525552655275528552929999553055315532553355342999955355536553755385539299995540554155425543554429999554555465547554855492999955505551555255535554299995555555655575558555929999556055615562556355642999955655566556755685569299995570557155725573557429999557555765577557855792999955805581558255835584299995585558655875588558929999559055915592559355942999955955596559755985599299995600560156025603560429999560556065607560856092999956105611561256135614299995615561656175618561929999562056215622562356242999956255626562756285629299995630563156325633563429999563556365637563856392999956405641564256435644299995645564656475648564929999565056515652565356542999956555656565756585659299995660566156625663566429999566556665667566856692999956705671567256735674299995675567656775678567929999568056815682568356842999956855686568756885689299995690569156925693569429999569556965697569856992999957005701570257035704299995705570657075708570929999571057115712571357142999957155716571757185719299995720572157225723572429999572557265727572857292999957305731573257335734299995735573657375738573929999574057415742574357442999957455746574757485749299995750575157525753575429999575557565757575857592999957605761576257635764299995765576657675768576929999577057715772577357742999957755776577757785779299995780578157825783578429999578557865787578857892999957905791579257935794299995795579657975798579929999580058015802580358042999958055806580758085809299995810581158125813581429999581558165817581858192999958205821582258235824299995825582658275828582929999583058315832583358342999958355836583758385839299995840584158425843584429999584558465847584858492999958505851585258535854299995855585658575858585929999586058615862586358642999958655866586758685869299995870587158725873587429999587558765877587858792999958805881588258835884299995885588658875888588929999589058915892589358942999958955896589758985899299995900590159025903590429999590559065907590859092999959105911591259135914299995915591659175918591929999592059215922592359242999959255926592759285929299995930593159325933593429999593559365937593859392999959405941594259435944299995945594659475948594929999595059515952595359542999959555956595759585959299995960596159625963596429999596559665967596859692999959705971597259735974299995975597659775978597929999598059815982598359842999959855986598759885989299995990599159925993599429999599559965997599859992999960006001600260036004299996005600660076008600929999601060116012601360142999960156016601760186019299996020602160226023602429999602560266027602860292999960306031603260336034299996035603660376038603929999604060416042604360442999960456046604760486049299996050605160526053605429999605560566057605860592999960606061606260636064299996065606660676068606929999607060716072607360742999960756076607760786079299996080608160826083608429999608560866087608860892999960906091609260936094299996095609660976098609929999610061016102610361042999961056106610761086109299996110611161126113611429999611561166117611861192999961206121612261236124299996125612661276128612929999613061316132613361342999961356136613761386139299996140614161426143614429999614561466147614861492999961506151615261536154299996155615661576158615929999616061616162616361642999961656166616761686169299996170617161726173617429999617561766177617861792999961806181618261836184299996185618661876188618929999619061916192619361942999961956196619761986199299996200620162026203620429999620562066207620862092999962106211621262136214299996215621662176218621929999622062216222622362242999962256226622762286229299996230623162326233623429999623562366237623862392999962406241624262436244299996245624662476248624929999625062516252625362542999962556256625762586259299996260626162626263626429999626562666267626862692999962706271627262736274299996275627662776278627929999628062816282628362842999962856286628762886289299996290629162926293629429999629562966297629862992999963006301630263036304299996305630663076308630929999631063116312631363142999963156316631763186319299996320632163226323632429999632563266327632863292999963306331633263336334299996335633663376338633929999634063416342634363442999963456346634763486349299996350635163526353635429999635563566357635863592999963606361636263636364299996365636663676368636929999637063716372637363742999963756376637763786379299996380638163826383638429999638563866387638863892999963906391639263936394299996395639663976398639929999640064016402640364042999964056406640764086409299996410641164126413641429999641564166417641864192999964206421642264236424299996425642664276428642929999643064316432643364342999964356436643764386439299996440644164426443644429999644564466447644864492999964506451645264536454299996455645664576458645929999646064616462646364642999964656466646764686469299996470647164726473647429999647564766477647864792999964806481648264836484299996485648664876488648929999649064916492649364942999964956496649764986499299996500650165026503650429999650565066507650865092999965106511651265136514299996515651665176518651929999652065216522652365242999965256526652765286529299996530653165326533653429999653565366537653865392999965406541654265436544299996545654665476548654929999655065516552655365542999965556556655765586559299996560656165626563656429999656565666567656865692999965706571657265736574299996575657665776578657929999658065816582658365842999965856586658765886589299996590659165926593659429999659565966597659865992999966006601660266036604299996605660666076608660929999661066116612661366142999966156616661766186619299996620662166226623662429999662566266627662866292999966306631663266336634299996635663666376638663929999664066416642664366442999966456646664766486649299996650665166526653665429999665566566657665866592999966606661666266636664299996665666666676668666929999667066716672667366742999966756676667766786679299996680668166826683668429999668566866687668866892999966906691669266936694299996695669666976698669929999670067016702670367042999967056706670767086709299996710671167126713671429999671567166717671867192999967206721672267236724299996725672667276728672929999673067316732673367342999967356736673767386739299996740674167426743674429999674567466747674867492999967506751675267536754299996755675667576758675929999676067616762676367642999967656766676767686769299996770677167726773677429999677567766777677867792999967806781678267836784299996785678667876788678929999679067916792679367942999967956796679767986799299996800680168026803680429999680568066807680868092999968106811681268136814299996815681668176818681929999682068216822682368242999968256826682768286829299996830683168326833683429999683568366837683868392999968406841684268436844299996845684668476848684929999685068516852685368542999968556856685768586859299996860686168626863686429999686568666867686868692999968706871687268736874299996875687668776878687929999688068816882688368842999968856886688768886889299996890689168926893689429999689568966897689868992999969006901690269036904299996905690669076908690929999691069116912691369142999969156916691769186919299996920692169226923692429999692569266927692869292999969306931693269336934299996935693669376938693929999694069416942694369442999969456946694769486949299996950695169526953695429999695569566957695869592999969606961696269636964299996965696669676968696929999697069716972697369742999969756976697769786979299996980698169826983698429999698569866987698869892999969906991699269936994299996995699669976998699929999700070017002700370042999970057006700770087009299997010701170127013701429999701570167017701870192999970207021702270237024299997025702670277028702929999703070317032703370342999970357036703770387039299997040704170427043704429999704570467047704870492999970507051705270537054299997055705670577058705929999706070617062706370642999970657066706770687069299997070707170727073707429999707570767077707870792999970807081708270837084299997085708670877088708929999709070917092709370942999970957096709770987099299997100710171027103710429999710571067107710871092999971107111711271137114299997115711671177118711929999712071217122712371242999971257126712771287129299997130713171327133713429999713571367137713871392999971407141714271437144299997145714671477148714929999715071517152715371542999971557156715771587159299997160716171627163716429999716571667167716871692999971707171717271737174299997175717671777178717929999718071817182718371842999971857186718771887189299997190719171927193719429999719571967197719871992999972007201720272037204299997205720672077208720929999721072117212721372142999972157216721772187219299997220722172227223722429999722572267227722872292999972307231723272337234299997235723672377238723929999724072417242724372442999972457246724772487249299997250725172527253725429999725572567257725872592999972607261726272637264299997265726672677268726929999727072717272727372742999972757276727772787279299997280728172827283728429999728572867287728872892999972907291729272937294299997295729672977298729929999730073017302730373042999973057306730773087309299997310731173127313731429999731573167317731873192999973207321732273237324299997325732673277328732929999733073317332733373342999973357336733773387339299997340734173427343734429999734573467347734873492999973507351735273537354299997355735673577358735929999736073617362736373642999973657366736773687369299997370737173727373737429999737573767377737873792999973807381738273837384299997385738673877388738929999739073917392739373942999973957396739773987399299997400740174027403740429999740574067407740874092999974107411741274137414299997415741674177418741929999742074217422742374242999974257426742774287429299997430743174327433743429999743574367437743874392999974407441744274437444299997445744674477448744929999745074517452745374542999974557456745774587459299997460746174627463746429999746574667467746874692999974707471747274737474299997475747674777478747929999748074817482748374842999974857486748774887489299997490749174927493749429999749574967497749874992999975007501750275037504299997505750675077508750929999751075117512751375142999975157516751775187519299997520752175227523752429999752575267527752875292999975307531753275337534299997535753675377538753929999754075417542754375442999975457546754775487549299997550755175527553755429999755575567557755875592999975607561756275637564299997565756675677568756929999757075717572757375742999975757576757775787579299997580758175827583758429999758575867587758875892999975907591759275937594299997595759675977598759929999760076017602760376042999976057606760776087609299997610761176127613761429999761576167617761876192999976207621762276237624299997625762676277628762929999763076317632763376342999976357636763776387639299997640764176427643764429999764576467647764876492999976507651765276537654299997655765676577658765929999766076617662766376642999976657666766776687669299997670767176727673767429999767576767677767876792999976807681768276837684299997685768676877688768929999769076917692769376942999976957696769776987699299997700770177027703770429999770577067707770877092999977107711771277137714299997715771677177718771929999772077217722772377242999977257726772777287729299997730773177327733773429999773577367737773877392999977407741774277437744299997745774677477748774929999775077517752775377542999977557756775777587759299997760776177627763776429999776577667767776877692999977707771777277737774299997775777677777778777929999778077817782778377842999977857786778777887789299997790779177927793779429999779577967797779877992999978007801780278037804299997805780678077808780929999781078117812781378142999978157816781778187819299997820782178227823782429999782578267827782878292999978307831783278337834299997835783678377838783929999784078417842784378442999978457846784778487849299997850785178527853785429999785578567857785878592999978607861786278637864299997865786678677868786929999787078717872787378742999978757876787778787879299997880788178827883788429999788578867887788878892999978907891789278937894299997895789678977898789929999790079017902790379042999979057906790779087909299997910791179127913791429999791579167917791879192999979207921792279237924299997925792679277928792929999793079317932793379342999979357936793779387939299997940794179427943794429999794579467947794879492999979507951795279537954299997955795679577958795929999796079617962796379642999979657966796779687969299997970797179727973797429999797579767977797879792999979807981798279837984299997985798679877988798929999799079917992799379942999979957996799779987999299998000800180028003800429999800580068007800880092999980108011801280138014299998015801680178018801929999802080218022802380242999980258026802780288029299998030803180328033803429999803580368037803880392999980408041804280438044299998045804680478048804929999805080518052805380542999980558056805780588059299998060806180628063806429999806580668067806880692999980708071807280738074299998075807680778078807929999808080818082808380842999980858086808780888089299998090809180928093809429999809580968097809880992999981008101810281038104299998105810681078108810929999811081118112811381142999981158116811781188119299998120812181228123812429999812581268127812881292999981308131813281338134299998135813681378138813929999814081418142814381442999981458146814781488149299998150815181528153815429999815581568157815881592999981608161816281638164299998165816681678168816929999817081718172817381742999981758176817781788179299998180818181828183818429999818581868187818881892999981908191819281938194299998195819681978198819929999820082018202820382042999982058206820782088209299998210821182128213821429999821582168217821882192999982208221822282238224299998225822682278228822929999823082318232823382342999982358236823782388239299998240824182428243824429999824582468247824882492999982508251825282538254299998255825682578258825929999826082618262826382642999982658266826782688269299998270827182728273827429999827582768277827882792999982808281828282838284299998285828682878288828929999829082918292829382942999982958296829782988299299998300830183028303830429999830583068307830883092999983108311831283138314299998315831683178318831929999832083218322832383242999983258326832783288329299998330833183328333833429999833583368337833883392999983408341834283438344299998345834683478348834929999835083518352835383542999983558356835783588359299998360836183628363836429999836583668367836883692999983708371837283738374299998375837683778378837929999838083818382838383842999983858386838783888389299998390839183928393839429999839583968397839883992999984008401840284038404299998405840684078408840929999841084118412841384142999984158416841784188419299998420842184228423842429999842584268427842884292999984308431843284338434299998435843684378438843929999844084418442844384442999984458446844784488449299998450845184528453845429999845584568457845884592999984608461846284638464299998465846684678468846929999847084718472847384742999984758476847784788479299998480848184828483848429999848584868487848884892999984908491849284938494299998495849684978498849929999850085018502850385042999985058506850785088509299998510851185128513851429999851585168517851885192999985208521852285238524299998525852685278528852929999853085318532853385342999985358536853785388539299998540854185428543854429999854585468547854885492999985508551855285538554299998555855685578558855929999856085618562856385642999985658566856785688569299998570857185728573857429999857585768577857885792999985808581858285838584299998585858685878588858929999859085918592859385942999985958596859785988599299998600860186028603860429999860586068607860886092999986108611861286138614299998615861686178618861929999862086218622862386242999986258626862786288629299998630863186328633863429999863586368637863886392999986408641864286438644299998645864686478648864929999865086518652865386542999986558656865786588659299998660866186628663866429999866586668667866886692999986708671867286738674299998675867686778678867929999868086818682868386842999986858686868786888689299998690869186928693869429999869586968697869886992999987008701870287038704299998705870687078708870929999871087118712871387142999987158716871787188719299998720872187228723872429999872587268727872887292999987308731873287338734299998735873687378738873929999874087418742874387442999987458746874787488749299998750875187528753875429999875587568757875887592999987608761876287638764299998765876687678768876929999877087718772877387742999987758776877787788779299998780878187828783878429999878587868787878887892999987908791879287938794299998795879687978798879929999880088018802880388042999988058806880788088809299998810881188128813881429999881588168817881888192999988208821882288238824299998825882688278828882929999883088318832883388342999988358836883788388839299998840884188428843884429999884588468847884888492999988508851885288538854299998855885688578858885929999886088618862886388642999988658866886788688869299998870887188728873887429999887588768877887888792999988808881888288838884299998885888688878888888929999889088918892889388942999988958896889788988899299998900890189028903890429999890589068907890889092999989108911891289138914299998915891689178918891929999892089218922892389242999989258926892789288929299998930893189328933893429999893589368937893889392999989408941894289438944299998945894689478948894929999895089518952895389542999989558956895789588959299998960896189628963896429999896589668967896889692999989708971897289738974299998975897689778978897929999898089818982898389842999989858986898789888989299998990899189928993899429999899589968997899889992999990009001900290039004299999005900690079008900929999901090119012901390142999990159016901790189019299999020902190229023902429999902590269027902890292999990309031903290339034299999035903690379038903929999904090419042904390442999990459046904790489049299999050905190529053905429999905590569057905890592999990609061906290639064299999065906690679068906929999907090719072907390742999990759076907790789079299999080908190829083908429999908590869087908890892999990909091909290939094299999095909690979098909929999910091019102910391042999991059106910791089109299999110911191129113911429999911591169117911891192999991209121912291239124299999125912691279128912929999913091319132913391342999991359136913791389139299999140914191429143914429999914591469147914891492999991509151915291539154299999155915691579158915929999916091619162916391642999991659166916791689169299999170917191729173917429999917591769177917891792999991809181918291839184299999185918691879188918929999919091919192919391942999991959196919791989199299999200920192029203920429999920592069207920892092999992109211921292139214299999215921692179218921929999922092219222922392242999992259226922792289229299999230923192329233923429999923592369237923892392999992409241924292439244299999245924692479248924929999925092519252925392542999992559256925792589259299999260926192629263926429999926592669267926892692999992709271927292739274299999275927692779278927929999928092819282928392842999992859286928792889289299999290929192929293929429999929592969297929892992999993009301930293039304299999305930693079308930929999931093119312931393142999993159316931793189319299999320932193229323932429999932593269327932893292999993309331933293339334299999335933693379338933929999934093419342934393442999993459346934793489349299999350935193529353935429999935593569357935893592999993609361936293639364299999365936693679368936929999937093719372937393742999993759376937793789379299999380938193829383938429999938593869387938893892999993909391939293939394299999395939693979398939929999940094019402940394042999994059406940794089409299999410941194129413941429999941594169417941894192999994209421942294239424299999425942694279428942929999943094319432943394342999994359436943794389439299999440944194429443944429999944594469447944894492999994509451945294539454299999455945694579458945929999946094619462946394642999994659466946794689469299999470947194729473947429999947594769477947894792999994809481948294839484299999485948694879488948929999949094919492949394942999994959496949794989499299999500950195029503950429999950595069507950895092999995109511951295139514299999515951695179518951929999952095219522952395242999995259526952795289529299999530953195329533953429999953595369537953895392999995409541954295439544299999545954695479548954929999955095519552955395542999995559556955795589559299999560956195629563956429999956595669567956895692999995709571957295739574299999575957695779578957929999958095819582958395842999995859586958795889589299999590959195929593959429999959595969597959895992999996009601960296039604299999605960696079608960929999961096119612961396142999996159616961796189619299999620962196229623962429999962596269627962896292999996309631963296339634299999635963696379638963929999964096419642964396442999996459646964796489649299999650965196529653965429999965596569657965896592999996609661966296639664299999665966696679668966929999967096719672967396742999996759676967796789679299999680968196829683968429999968596869687968896892999996909691969296939694299999695969696979698969929999970097019702970397042999997059706970797089709299999710971197129713971429999971597169717971897192999997209721972297239724299999725972697279728972929999973097319732973397342999997359736973797389739299999740974197429743974429999974597469747974897492999997509751975297539754299999755975697579758975929999976097619762976397642999997659766976797689769299999770977197729773977429999977597769777977897792999997809781978297839784299999785978697879788978929999979097919792979397942999997959796979797989799299999800980198029803980429999980598069807980898092999998109811981298139814299999815981698179818981929999982098219822982398242999998259826982798289829299999830983198329833983429999983598369837983898392999998409841984298439844299999845984698479848984929999985098519852985398542999998559856985798589859299999860986198629863986429999986598669867986898692999998709871987298739874299999875987698779878987929999988098819882988398842999998859886988798889889299999890989198929893989429999989598969897989898992999999009901990299039904299999905990699079908990929999991099119912991399142999999159916991799189919299999920992199229923992429999992599269927992899292999999309931993299339934299999935993699379938993929999994099419942994399442999999459946994799489949299999950995199529953995429999995599569957995899592999999609961996299639964299999965996699679968996929999997099719972997399742999999759976997799789979299999980998199829983998429999998599869987998899892999999909991999299939994299999995999699979998999929999100001000110002100031000429999100051000610007100081000929999100101001110012100131001429999100151001610017100181001929999100201002110022100231002429999100251002610027100281002929999100301003110032100331003429999100351003610037100381003929999100401004110042100431004429999100451004610047100481004929999100501005110052100531005429999100551005610057100581005929999100601006110062100631006429999100651006610067100681006929999100701007110072100731007429999100751007610077100781007929999100801008110082100831008429999100851008610087100881008929999100901009110092100931009429999100951009610097100981009929999101001010110102101031010429999101051010610107101081010929999101101011110112101131011429999101151011610117101181011929999101201012110122101231012429999101251012610127101281012929999101301013110132101331013429999101351013610137101381013929999101401014110142101431014429999101451014610147101481014929999101501015110152101531015429999101551015610157101581015929999101601016110162101631016429999101651016610167101681016929999101701017110172101731017429999101751017610177101781017929999101801018110182101831018429999101851018610187101881018929999101901019110192101931019429999101951019610197101981019929999102001020110202102031020429999102051020610207102081020929999102101021110212102131021429999102151021610217102181021929999102201022110222102231022429999102251022610227102281022929999102301023110232102331023429999102351023610237102381023929999102401024110242102431024429999102451024610247102481024929999102501025110252102531025429999102551025610257102581025929999102601026110262102631026429999102651026610267102681026929999102701027110272102731027429999102751027610277102781027929999102801028110282102831028429999102851028610287102881028929999102901029110292102931029429999102951029610297102981029929999103001030110302103031030429999103051030610307103081030929999103101031110312103131031429999103151031610317103181031929999103201032110322103231032429999103251032610327103281032929999103301033110332103331033429999103351033610337103381033929999103401034110342103431034429999103451034610347103481034929999103501035110352103531035429999103551035610357103581035929999103601036110362103631036429999103651036610367103681036929999103701037110372103731037429999103751037610377103781037929999103801038110382103831038429999103851038610387103881038929999103901039110392103931039429999103951039610397103981039929999104001040110402104031040429999104051040610407104081040929999104101041110412104131041429999104151041610417104181041929999104201042110422104231042429999104251042610427104281042929999104301043110432104331043429999104351043610437104381043929999104401044110442104431044429999104451044610447104481044929999104501045110452104531045429999104551045610457104581045929999104601046110462104631046429999104651046610467104681046929999104701047110472104731047429999104751047610477104781047929999104801048110482104831048429999104851048610487104881048929999104901049110492104931049429999104951049610497104981049929999105001050110502105031050429999105051050610507105081050929999105101051110512105131051429999105151051610517105181051929999105201052110522105231052429999105251052610527105281052929999105301053110532105331053429999105351053610537105381053929999105401054110542105431054429999105451054610547105481054929999105501055110552105531055429999105551055610557105581055929999105601056110562105631056429999105651056610567105681056929999105701057110572105731057429999105751057610577105781057929999105801058110582105831058429999105851058610587105881058929999105901059110592105931059429999105951059610597105981059929999106001060110602106031060429999106051060610607106081060929999106101061110612106131061429999106151061610617106181061929999106201062110622106231062429999106251062610627106281062929999106301063110632106331063429999106351063610637106381063929999106401064110642106431064429999106451064610647106481064929999106501065110652106531065429999106551065610657106581065929999106601066110662106631066429999106651066610667106681066929999106701067110672106731067429999106751067610677106781067929999106801068110682106831068429999106851068610687106881068929999106901069110692106931069429999106951069610697106981069929999107001070110702107031070429999107051070610707107081070929999107101071110712107131071429999107151071610717107181071929999107201072110722107231072429999107251072610727107281072929999107301073110732107331073429999107351073610737107381073929999107401074110742107431074429999107451074610747107481074929999107501075110752107531075429999107551075610757107581075929999107601076110762107631076429999107651076610767107681076929999107701077110772107731077429999107751077610777107781077929999107801078110782107831078429999107851078610787107881078929999107901079110792107931079429999107951079610797107981079929999108001080110802108031080429999108051080610807108081080929999108101081110812108131081429999108151081610817108181081929999108201082110822108231082429999108251082610827108281082929999108301083110832108331083429999108351083610837108381083929999108401084110842108431084429999108451084610847108481084929999108501085110852108531085429999108551085610857108581085929999108601086110862108631086429999108651086610867108681086929999108701087110872108731087429999108751087610877108781087929999108801088110882108831088429999108851088610887108881088929999108901089110892108931089429999108951089610897108981089929999109001090110902109031090429999109051090610907109081090929999109101091110912109131091429999109151091610917109181091929999109201092110922109231092429999109251092610927109281092929999109301093110932109331093429999109351093610937109381093929999109401094110942109431094429999109451094610947109481094929999109501095110952109531095429999109551095610957109581095929999109601096110962109631096429999109651096610967109681096929999109701097110972109731097429999109751097610977109781097929999109801098110982109831098429999109851098610987109881098929999109901099110992109931099429999109951099610997109981099929999110001100111002110031100429999110051100611007110081100929999110101101111012110131101429999110151101611017110181101929999110201102111022110231102429999110251102611027110281102929999110301103111032110331103429999110351103611037110381103929999110401104111042110431104429999110451104611047110481104929999110501105111052110531105429999110551105611057110581105929999110601106111062110631106429999110651106611067110681106929999110701107111072110731107429999110751107611077110781107929999110801108111082110831108429999110851108611087110881108929999110901109111092110931109429999110951109611097110981109929999111001110111102111031110429999111051110611107111081110929999111101111111112111131111429999111151111611117111181111929999111201112111122111231112429999111251112611127111281112929999111301113111132111331113429999111351113611137111381113929999111401114111142111431114429999111451114611147111481114929999111501115111152111531115429999111551115611157111581115929999111601116111162111631116429999111651116611167111681116929999111701117111172111731117429999111751117611177111781117929999111801118111182111831118429999111851118611187111881118929999111901119111192111931119429999111951119611197111981119929999112001120111202112031120429999112051120611207112081120929999112101121111212112131121429999112151121611217112181121929999112201122111222112231122429999112251122611227112281122929999112301123111232112331123429999112351123611237112381123929999112401124111242112431124429999112451124611247112481124929999112501125111252112531125429999112551125611257112581125929999112601126111262112631126429999112651126611267112681126929999112701127111272112731127429999112751127611277112781127929999112801128111282112831128429999112851128611287112881128929999112901129111292112931129429999112951129611297112981129929999113001130111302113031130429999113051130611307113081130929999113101131111312113131131429999113151131611317113181131929999113201132111322113231132429999113251132611327113281132929999113301133111332113331133429999113351133611337113381133929999113401134111342113431134429999113451134611347113481134929999113501135111352113531135429999113551135611357113581135929999113601136111362113631136429999113651136611367113681136929999113701137111372113731137429999113751137611377113781137929999113801138111382113831138429999113851138611387113881138929999113901139111392113931139429999113951139611397113981139929999114001140111402114031140429999114051140611407114081140929999114101141111412114131141429999114151141611417114181141929999114201142111422114231142429999114251142611427114281142929999114301143111432114331143429999114351143611437114381143929999114401144111442114431144429999114451144611447114481144929999114501145111452114531145429999114551145611457114581145929999114601146111462114631146429999114651146611467114681146929999114701147111472114731147429999114751147611477114781147929999114801148111482114831148429999114851148611487114881148929999114901149111492114931149429999114951149611497114981149929999115001150111502115031150429999115051150611507115081150929999115101151111512115131151429999115151151611517115181151929999115201152111522115231152429999115251152611527115281152929999115301153111532115331153429999115351153611537115381153929999115401154111542115431154429999115451154611547115481154929999115501155111552115531155429999115551155611557115581155929999115601156111562115631156429999115651156611567115681156929999115701157111572115731157429999115751157611577115781157929999115801158111582115831158429999115851158611587115881158929999115901159111592115931159429999115951159611597115981159929999116001160111602116031160429999116051160611607116081160929999116101161111612116131161429999116151161611617116181161929999116201162111622116231162429999116251162611627116281162929999116301163111632116331163429999116351163611637116381163929999116401164111642116431164429999116451164611647116481164929999116501165111652116531165429999116551165611657116581165929999116601166111662116631166429999116651166611667116681166929999116701167111672116731167429999116751167611677116781167929999116801168111682116831168429999116851168611687116881168929999116901169111692116931169429999116951169611697116981169929999117001170111702117031170429999117051170611707117081170929999117101171111712117131171429999117151171611717117181171929999117201172111722117231172429999117251172611727117281172929999117301173111732117331173429999117351173611737117381173929999117401174111742117431174429999117451174611747117481174929999117501175111752117531175429999117551175611757117581175929999117601176111762117631176429999117651176611767117681176929999117701177111772117731177429999117751177611777117781177929999117801178111782117831178429999117851178611787117881178929999117901179111792117931179429999117951179611797117981179929999118001180111802118031180429999118051180611807118081180929999118101181111812118131181429999118151181611817118181181929999118201182111822118231182429999118251182611827118281182929999118301183111832118331183429999118351183611837118381183929999118401184111842118431184429999118451184611847118481184929999118501185111852118531185429999118551185611857118581185929999118601186111862118631186429999118651186611867118681186929999118701187111872118731187429999118751187611877118781187929999118801188111882118831188429999118851188611887118881188929999118901189111892118931189429999118951189611897118981189929999119001190111902119031190429999119051190611907119081190929999119101191111912119131191429999119151191611917119181191929999119201192111922119231192429999119251192611927119281192929999119301193111932119331193429999119351193611937119381193929999119401194111942119431194429999119451194611947119481194929999119501195111952119531195429999119551195611957119581195929999119601196111962119631196429999119651196611967119681196929999119701197111972119731197429999119751197611977119781197929999119801198111982119831198429999119851198611987119881198929999119901199111992119931199429999119951199611997119981199929999120001200112002120031200429999120051200612007120081200929999120101201112012120131201429999120151201612017120181201929999120201202112022120231202429999120251202612027120281202929999120301203112032120331203429999120351203612037120381203929999120401204112042120431204429999120451204612047120481204929999120501205112052120531205429999120551205612057120581205929999120601206112062120631206429999120651206612067120681206929999120701207112072120731207429999120751207612077120781207929999120801208112082120831208429999120851208612087120881208929999120901209112092120931209429999120951209612097120981209929999121001210112102121031210429999121051210612107121081210929999121101211112112121131211429999121151211612117121181211929999121201212112122121231212429999121251212612127121281212929999121301213112132121331213429999121351213612137121381213929999121401214112142121431214429999121451214612147121481214929999121501215112152121531215429999121551215612157121581215929999121601216112162121631216429999121651216612167121681216929999121701217112172121731217429999121751217612177121781217929999121801218112182121831218429999121851218612187121881218929999121901219112192121931219429999121951219612197121981219929999122001220112202122031220429999122051220612207122081220929999122101221112212122131221429999122151221612217122181221929999122201222112222122231222429999122251222612227122281222929999122301223112232122331223429999122351223612237122381223929999122401224112242122431224429999122451224612247122481224929999122501225112252122531225429999122551225612257122581225929999122601226112262122631226429999122651226612267122681226929999122701227112272122731227429999122751227612277122781227929999122801228112282122831228429999122851228612287122881228929999122901229112292122931229429999122951229612297122981229929999123001230112302123031230429999123051230612307123081230929999123101231112312123131231429999123151231612317123181231929999123201232112322123231232429999123251232612327123281232929999123301233112332123331233429999123351233612337123381233929999123401234112342123431234429999123451234612347123481234929999123501235112352123531235429999123551235612357123581235929999123601236112362123631236429999123651236612367123681236929999123701237112372123731237429999123751237612377123781237929999123801238112382123831238429999123851238612387123881238929999123901239112392123931239429999123951239612397123981239929999124001240112402124031240429999124051240612407124081240929999124101241112412124131241429999124151241612417124181241929999124201242112422124231242429999124251242612427124281242929999124301243112432124331243429999124351243612437124381243929999124401244112442124431244429999124451244612447124481244929999124501245112452124531245429999124551245612457124581245929999124601246112462124631246429999124651246612467124681246929999124701247112472124731247429999124751247612477124781247929999124801248112482124831248429999124851248612487124881248929999124901249112492124931249429999124951249612497124981249929999125001250112502125031250429999125051250612507125081250929999125101251112512125131251429999125151251612517125181251929999125201252112522125231252429999125251252612527125281252929999125301253112532125331253429999125351253612537125381253929999125401254112542125431254429999125451254612547125481254929999125501255112552125531255429999125551255612557125581255929999125601256112562125631256429999125651256612567125681256929999125701257112572125731257429999125751257612577125781257929999125801258112582125831258429999125851258612587125881258929999125901259112592125931259429999125951259612597125981259929999126001260112602126031260429999126051260612607126081260929999126101261112612126131261429999126151261612617126181261929999126201262112622126231262429999126251262612627126281262929999126301263112632126331263429999126351263612637126381263929999126401264112642126431264429999126451264612647126481264929999126501265112652126531265429999126551265612657126581265929999126601266112662126631266429999126651266612667126681266929999126701267112672126731267429999126751267612677126781267929999126801268112682126831268429999126851268612687126881268929999126901269112692126931269429999126951269612697126981269929999127001270112702127031270429999127051270612707127081270929999127101271112712127131271429999127151271612717127181271929999127201272112722127231272429999127251272612727127281272929999127301273112732127331273429999127351273612737127381273929999127401274112742127431274429999127451274612747127481274929999127501275112752127531275429999127551275612757127581275929999127601276112762127631276429999127651276612767127681276929999127701277112772127731277429999127751277612777127781277929999127801278112782127831278429999127851278612787127881278929999127901279112792127931279429999127951279612797127981279929999128001280112802128031280429999128051280612807128081280929999128101281112812128131281429999128151281612817128181281929999128201282112822128231282429999128251282612827128281282929999128301283112832128331283429999128351283612837128381283929999128401284112842128431284429999128451284612847128481284929999128501285112852128531285429999128551285612857128581285929999128601286112862128631286429999128651286612867128681286929999128701287112872128731287429999128751287612877128781287929999128801288112882128831288429999128851288612887128881288929999128901289112892128931289429999128951289612897128981289929999129001290112902129031290429999129051290612907129081290929999129101291112912129131291429999129151291612917129181291929999129201292112922129231292429999129251292612927129281292929999129301293112932129331293429999129351293612937129381293929999129401294112942129431294429999129451294612947129481294929999129501295112952129531295429999129551295612957129581295929999129601296112962129631296429999129651296612967129681296929999129701297112972129731297429999129751297612977129781297929999129801298112982129831298429999129851298612987129881298929999129901299112992129931299429999129951299612997129981299929999130001300113002130031300429999130051300613007130081300929999130101301113012130131301429999130151301613017130181301929999130201302113022130231302429999130251302613027130281302929999130301303113032130331303429999130351303613037130381303929999130401304113042130431304429999130451304613047130481304929999130501305113052130531305429999130551305613057130581305929999130601306113062130631306429999130651306613067130681306929999130701307113072130731307429999130751307613077130781307929999130801308113082130831308429999130851308613087130881308929999130901309113092130931309429999130951309613097130981309929999131001310113102131031310429999131051310613107131081310929999131101311113112131131311429999131151311613117131181311929999131201312113122131231312429999131251312613127131281312929999131301313113132131331313429999131351313613137131381313929999131401314113142131431314429999131451314613147131481314929999131501315113152131531315429999131551315613157131581315929999131601316113162131631316429999131651316613167131681316929999131701317113172131731317429999131751317613177131781317929999131801318113182131831318429999131851318613187131881318929999131901319113192131931319429999131951319613197131981319929999132001320113202132031320429999132051320613207132081320929999132101321113212132131321429999132151321613217132181321929999132201322113222132231322429999132251322613227132281322929999132301323113232132331323429999132351323613237132381323929999132401324113242132431324429999132451324613247132481324929999132501325113252132531325429999132551325613257132581325929999132601326113262132631326429999132651326613267132681326929999132701327113272132731327429999132751327613277132781327929999132801328113282132831328429999132851328613287132881328929999132901329113292132931329429999132951329613297132981329929999133001330113302133031330429999133051330613307133081330929999133101331113312133131331429999133151331613317133181331929999133201332113322133231332429999133251332613327133281332929999133301333113332133331333429999133351333613337133381333929999133401334113342133431334429999133451334613347133481334929999133501335113352133531335429999133551335613357133581335929999133601336113362133631336429999133651336613367133681336929999133701337113372133731337429999133751337613377133781337929999133801338113382133831338429999133851338613387133881338929999133901339113392133931339429999133951339613397133981339929999134001340113402134031340429999134051340613407134081340929999134101341113412134131341429999134151341613417134181341929999134201342113422134231342429999134251342613427134281342929999134301343113432134331343429999134351343613437134381343929999134401344113442134431344429999134451344613447134481344929999134501345113452134531345429999134551345613457134581345929999134601346113462134631346429999134651346613467134681346929999134701347113472134731347429999134751347613477134781347929999134801348113482134831348429999134851348613487134881348929999134901349113492134931349429999134951349613497134981349929999135001350113502135031350429999135051350613507135081350929999135101351113512135131351429999135151351613517135181351929999135201352113522135231352429999135251352613527135281352929999135301353113532135331353429999135351353613537135381353929999135401354113542135431354429999135451354613547135481354929999135501355113552135531355429999135551355613557135581355929999135601356113562135631356429999135651356613567135681356929999135701357113572135731357429999135751357613577135781357929999135801358113582135831358429999135851358613587135881358929999135901359113592135931359429999135951359613597135981359929999136001360113602136031360429999136051360613607136081360929999136101361113612136131361429999136151361613617136181361929999136201362113622136231362429999136251362613627136281362929999136301363113632136331363429999136351363613637136381363929999136401364113642136431364429999136451364613647136481364929999136501365113652136531365429999136551365613657136581365929999136601366113662136631366429999136651366613667136681366929999136701367113672136731367429999136751367613677136781367929999136801368113682136831368429999136851368613687136881368929999136901369113692136931369429999136951369613697136981369929999137001370113702137031370429999137051370613707137081370929999137101371113712137131371429999137151371613717137181371929999137201372113722137231372429999137251372613727137281372929999137301373113732137331373429999137351373613737137381373929999137401374113742137431374429999137451374613747137481374929999137501375113752137531375429999137551375613757137581375929999137601376113762137631376429999137651376613767137681376929999137701377113772137731377429999137751377613777137781377929999137801378113782137831378429999137851378613787137881378929999137901379113792137931379429999137951379613797137981379929999138001380113802138031380429999138051380613807138081380929999138101381113812138131381429999138151381613817138181381929999138201382113822138231382429999138251382613827138281382929999138301383113832138331383429999138351383613837138381383929999138401384113842138431384429999138451384613847138481384929999138501385113852138531385429999138551385613857138581385929999138601386113862138631386429999138651386613867138681386929999138701387113872138731387429999138751387613877138781387929999138801388113882138831388429999138851388613887138881388929999138901389113892138931389429999138951389613897138981389929999139001390113902139031390429999139051390613907139081390929999139101391113912139131391429999139151391613917139181391929999139201392113922139231392429999139251392613927139281392929999139301393113932139331393429999139351393613937139381393929999139401394113942139431394429999139451394613947139481394929999139501395113952139531395429999139551395613957139581395929999139601396113962139631396429999139651396613967139681396929999139701397113972139731397429999139751397613977139781397929999139801398113982139831398429999139851398613987139881398929999139901399113992139931399429999139951399613997139981399929999140001400114002140031400429999140051400614007140081400929999140101401114012140131401429999140151401614017140181401929999140201402114022140231402429999140251402614027140281402929999140301403114032140331403429999140351403614037140381403929999140401404114042140431404429999140451404614047140481404929999140501405114052140531405429999140551405614057140581405929999140601406114062140631406429999140651406614067140681406929999140701407114072140731407429999140751407614077140781407929999140801408114082140831408429999140851408614087140881408929999140901409114092140931409429999140951409614097140981409929999141001410114102141031410429999141051410614107141081410929999141101411114112141131411429999141151411614117141181411929999141201412114122141231412429999141251412614127141281412929999141301413114132141331413429999141351413614137141381413929999141401414114142141431414429999141451414614147141481414929999141501415114152141531415429999141551415614157141581415929999141601416114162141631416429999141651416614167141681416929999141701417114172141731417429999141751417614177141781417929999141801418114182141831418429999141851418614187141881418929999141901419114192141931419429999141951419614197141981419929999142001420114202142031420429999142051420614207142081420929999142101421114212142131421429999142151421614217142181421929999142201422114222142231422429999142251422614227142281422929999142301423114232142331423429999142351423614237142381423929999142401424114242142431424429999142451424614247142481424929999142501425114252142531425429999142551425614257142581425929999142601426114262142631426429999142651426614267142681426929999142701427114272142731427429999142751427614277142781427929999142801428114282142831428429999142851428614287142881428929999142901429114292142931429429999142951429614297142981429929999143001430114302143031430429999143051430614307143081430929999143101431114312143131431429999143151431614317143181431929999143201432114322143231432429999143251432614327143281432929999143301433114332143331433429999143351433614337143381433929999143401434114342143431434429999143451434614347143481434929999143501435114352143531435429999143551435614357143581435929999143601436114362143631436429999143651436614367143681436929999143701437114372143731437429999143751437614377143781437929999143801438114382143831438429999143851438614387143881438929999143901439114392143931439429999143951439614397143981439929999144001440114402144031440429999144051440614407144081440929999144101441114412144131441429999144151441614417144181441929999144201442114422144231442429999144251442614427144281442929999144301443114432144331443429999144351443614437144381443929999144401444114442144431444429999144451444614447144481444929999144501445114452144531445429999144551445614457144581445929999144601446114462144631446429999144651446614467144681446929999144701447114472144731447429999144751447614477144781447929999144801448114482144831448429999144851448614487144881448929999144901449114492144931449429999144951449614497144981449929999145001450114502145031450429999145051450614507145081450929999145101451114512145131451429999145151451614517145181451929999145201452114522145231452429999145251452614527145281452929999145301453114532145331453429999145351453614537145381453929999145401454114542145431454429999145451454614547145481454929999145501455114552145531455429999145551455614557145581455929999145601456114562145631456429999145651456614567145681456929999145701457114572145731457429999145751457614577145781457929999145801458114582145831458429999145851458614587145881458929999145901459114592145931459429999145951459614597145981459929999146001460114602146031460429999146051460614607146081460929999146101461114612146131461429999146151461614617146181461929999146201462114622146231462429999146251462614627146281462929999146301463114632146331463429999146351463614637146381463929999146401464114642146431464429999146451464614647146481464929999146501465114652146531465429999146551465614657146581465929999146601466114662146631466429999146651466614667146681466929999146701467114672146731467429999146751467614677146781467929999146801468114682146831468429999146851468614687146881468929999146901469114692146931469429999146951469614697146981469929999147001470114702147031470429999147051470614707147081470929999147101471114712147131471429999147151471614717147181471929999147201472114722147231472429999147251472614727147281472929999147301473114732147331473429999147351473614737147381473929999147401474114742147431474429999147451474614747147481474929999147501475114752147531475429999147551475614757147581475929999147601476114762147631476429999147651476614767147681476929999147701477114772147731477429999147751477614777147781477929999147801478114782147831478429999147851478614787147881478929999147901479114792147931479429999147951479614797147981479929999148001480114802148031480429999148051480614807148081480929999148101481114812148131481429999148151481614817148181481929999148201482114822148231482429999148251482614827148281482929999148301483114832148331483429999148351483614837148381483929999148401484114842148431484429999148451484614847148481484929999148501485114852148531485429999148551485614857148581485929999148601486114862148631486429999148651486614867148681486929999148701487114872148731487429999148751487614877148781487929999148801488114882148831488429999148851488614887148881488929999148901489114892148931489429999148951489614897148981489929999149001490114902149031490429999149051490614907149081490929999149101491114912149131491429999149151491614917149181491929999149201492114922149231492429999149251492614927149281492929999149301493114932149331493429999149351493614937149381493929999149401494114942149431494429999149451494614947149481494929999149501495114952149531495429999149551495614957149581495929999149601496114962149631496429999149651496614967149681496929999149701497114972149731497429999149751497614977149781497929999149801498114982149831498429999149851498614987149881498929999149901499114992149931499429999149951499614997149981499929999150001500115002150031500429999150051500615007150081500929999150101501115012150131501429999150151501615017150181501929999150201502115022150231502429999150251502615027150281502929999150301503115032150331503429999150351503615037150381503929999150401504115042150431504429999150451504615047150481504929999150501505115052150531505429999150551505615057150581505929999150601506115062150631506429999150651506615067150681506929999150701507115072150731507429999150751507615077150781507929999150801508115082150831508429999150851508615087150881508929999150901509115092150931509429999150951509615097150981509929999151001510115102151031510429999151051510615107151081510929999151101511115112151131511429999151151511615117151181511929999151201512115122151231512429999151251512615127151281512929999151301513115132151331513429999151351513615137151381513929999151401514115142151431514429999151451514615147151481514929999151501515115152151531515429999151551515615157151581515929999151601516115162151631516429999151651516615167151681516929999151701517115172151731517429999151751517615177151781517929999151801518115182151831518429999151851518615187151881518929999151901519115192151931519429999151951519615197151981519929999152001520115202152031520429999152051520615207152081520929999152101521115212152131521429999152151521615217152181521929999152201522115222152231522429999152251522615227152281522929999152301523115232152331523429999152351523615237152381523929999152401524115242152431524429999152451524615247152481524929999152501525115252152531525429999152551525615257152581525929999152601526115262152631526429999152651526615267152681526929999152701527115272152731527429999152751527615277152781527929999152801528115282152831528429999152851528615287152881528929999152901529115292152931529429999152951529615297152981529929999153001530115302153031530429999153051530615307153081530929999153101531115312153131531429999153151531615317153181531929999153201532115322153231532429999153251532615327153281532929999153301533115332153331533429999153351533615337153381533929999153401534115342153431534429999153451534615347153481534929999153501535115352153531535429999153551535615357153581535929999153601536115362153631536429999153651536615367153681536929999153701537115372153731537429999153751537615377153781537929999153801538115382153831538429999153851538615387153881538929999153901539115392153931539429999153951539615397153981539929999154001540115402154031540429999154051540615407154081540929999154101541115412154131541429999154151541615417154181541929999154201542115422154231542429999154251542615427154281542929999154301543115432154331543429999154351543615437154381543929999154401544115442154431544429999154451544615447154481544929999154501545115452154531545429999154551545615457154581545929999154601546115462154631546429999154651546615467154681546929999154701547115472154731547429999154751547615477154781547929999154801548115482154831548429999154851548615487154881548929999154901549115492154931549429999154951549615497154981549929999155001550115502155031550429999155051550615507155081550929999155101551115512155131551429999155151551615517155181551929999155201552115522155231552429999155251552615527155281552929999155301553115532155331553429999155351553615537155381553929999155401554115542155431554429999155451554615547155481554929999155501555115552155531555429999155551555615557155581555929999155601556115562155631556429999155651556615567155681556929999155701557115572155731557429999155751557615577155781557929999155801558115582155831558429999155851558615587155881558929999155901559115592155931559429999155951559615597155981559929999156001560115602156031560429999156051560615607156081560929999156101561115612156131561429999156151561615617156181561929999156201562115622156231562429999156251562615627156281562929999156301563115632156331563429999156351563615637156381563929999156401564115642156431564429999156451564615647156481564929999156501565115652156531565429999156551565615657156581565929999156601566115662156631566429999156651566615667156681566929999156701567115672156731567429999156751567615677156781567929999156801568115682156831568429999156851568615687156881568929999156901569115692156931569429999156951569615697156981569929999157001570115702157031570429999157051570615707157081570929999157101571115712157131571429999157151571615717157181571929999157201572115722157231572429999157251572615727157281572929999157301573115732157331573429999157351573615737157381573929999157401574115742157431574429999157451574615747157481574929999157501575115752157531575429999157551575615757157581575929999157601576115762157631576429999157651576615767157681576929999157701577115772157731577429999157751577615777157781577929999157801578115782157831578429999157851578615787157881578929999157901579115792157931579429999157951579615797157981579929999158001580115802158031580429999158051580615807158081580929999158101581115812158131581429999158151581615817158181581929999158201582115822158231582429999158251582615827158281582929999158301583115832158331583429999158351583615837158381583929999158401584115842158431584429999158451584615847158481584929999158501585115852158531585429999158551585615857158581585929999158601586115862158631586429999158651586615867158681586929999158701587115872158731587429999158751587615877158781587929999158801588115882158831588429999158851588615887158881588929999158901589115892158931589429999158951589615897158981589929999159001590115902159031590429999159051590615907159081590929999159101591115912159131591429999159151591615917159181591929999159201592115922159231592429999159251592615927159281592929999159301593115932159331593429999159351593615937159381593929999159401594115942159431594429999159451594615947159481594929999159501595115952159531595429999159551595615957159581595929999159601596115962159631596429999159651596615967159681596929999159701597115972159731597429999159751597615977159781597929999159801598115982159831598429999159851598615987159881598929999159901599115992159931599429999159951599615997159981599929999160001600116002160031600429999160051600616007160081600929999160101601116012160131601429999160151601616017160181601929999160201602116022160231602429999160251602616027160281602929999160301603116032160331603429999160351603616037160381603929999160401604116042160431604429999160451604616047160481604929999160501605116052160531605429999160551605616057160581605929999160601606116062160631606429999160651606616067160681606929999160701607116072160731607429999160751607616077160781607929999160801608116082160831608429999160851608616087160881608929999160901609116092160931609429999160951609616097160981609929999161001610116102161031610429999161051610616107161081610929999161101611116112161131611429999161151611616117161181611929999161201612116122161231612429999161251612616127161281612929999161301613116132161331613429999161351613616137161381613929999161401614116142161431614429999161451614616147161481614929999161501615116152161531615429999161551615616157161581615929999161601616116162161631616429999161651616616167161681616929999161701617116172161731617429999161751617616177161781617929999161801618116182161831618429999161851618616187161881618929999161901619116192161931619429999161951619616197161981619929999162001620116202162031620429999162051620616207162081620929999162101621116212162131621429999162151621616217162181621929999162201622116222162231622429999162251622616227162281622929999162301623116232162331623429999162351623616237162381623929999162401624116242162431624429999162451624616247162481624929999162501625116252162531625429999162551625616257162581625929999162601626116262162631626429999162651626616267162681626929999162701627116272162731627429999162751627616277162781627929999162801628116282162831628429999162851628616287162881628929999162901629116292162931629429999162951629616297162981629929999163001630116302163031630429999163051630616307163081630929999163101631116312163131631429999163151631616317163181631929999163201632116322163231632429999163251632616327163281632929999163301633116332163331633429999163351633616337163381633929999163401634116342163431634429999163451634616347163481634929999163501635116352163531635429999163551635616357163581635929999163601636116362163631636429999163651636616367163681636929999163701637116372163731637429999163751637616377163781637929999163801638116382163831638429999163851638616387163881638929999163901639116392163931639429999163951639616397163981639929999164001640116402164031640429999164051640616407164081640929999164101641116412164131641429999164151641616417164181641929999164201642116422164231642429999164251642616427164281642929999164301643116432164331643429999164351643616437164381643929999164401644116442164431644429999164451644616447164481644929999164501645116452164531645429999164551645616457164581645929999164601646116462164631646429999164651646616467164681646929999164701647116472164731647429999164751647616477164781647929999164801648116482164831648429999164851648616487164881648929999164901649116492164931649429999164951649616497164981649929999165001650116502165031650429999165051650616507165081650929999165101651116512165131651429999165151651616517165181651929999165201652116522165231652429999165251652616527165281652929999165301653116532165331653429999165351653616537165381653929999165401654116542165431654429999165451654616547165481654929999165501655116552165531655429999165551655616557165581655929999165601656116562165631656429999165651656616567165681656929999165701657116572165731657429999165751657616577165781657929999165801658116582165831658429999165851658616587165881658929999165901659116592165931659429999165951659616597165981659929999166001660116602166031660429999166051660616607166081660929999166101661116612166131661429999166151661616617166181661929999166201662116622166231662429999166251662616627166281662929999166301663116632166331663429999166351663616637166381663929999166401664116642166431664429999166451664616647166481664929999166501665116652166531665429999166551665616657166581665929999166601666116662166631666429999166651666616667166681666929999166701667116672166731667429999166751667616677166781667929999166801668116682166831668429999166851668616687166881668929999166901669116692166931669429999166951669616697166981669929999167001670116702167031670429999167051670616707167081670929999167101671116712167131671429999167151671616717167181671929999167201672116722167231672429999167251672616727167281672929999167301673116732167331673429999167351673616737167381673929999167401674116742167431674429999167451674616747167481674929999167501675116752167531675429999167551675616757167581675929999167601676116762167631676429999167651676616767167681676929999167701677116772167731677429999167751677616777167781677929999167801678116782167831678429999167851678616787167881678929999167901679116792167931679429999167951679616797167981679929999168001680116802168031680429999168051680616807168081680929999168101681116812168131681429999168151681616817168181681929999168201682116822168231682429999168251682616827168281682929999168301683116832168331683429999168351683616837168381683929999168401684116842168431684429999168451684616847168481684929999168501685116852168531685429999168551685616857168581685929999168601686116862168631686429999168651686616867168681686929999168701687116872168731687429999168751687616877168781687929999168801688116882168831688429999168851688616887168881688929999168901689116892168931689429999168951689616897168981689929999169001690116902169031690429999169051690616907169081690929999169101691116912169131691429999169151691616917169181691929999169201692116922169231692429999169251692616927169281692929999169301693116932169331693429999169351693616937169381693929999169401694116942169431694429999169451694616947169481694929999169501695116952169531695429999169551695616957169581695929999169601696116962169631696429999169651696616967169681696929999169701697116972169731697429999169751697616977169781697929999169801698116982169831698429999169851698616987169881698929999169901699116992169931699429999169951699616997169981699929999170001700117002170031700429999170051700617007170081700929999170101701117012170131701429999170151701617017170181701929999170201702117022170231702429999170251702617027170281702929999170301703117032170331703429999170351703617037170381703929999170401704117042170431704429999170451704617047170481704929999170501705117052170531705429999170551705617057170581705929999170601706117062170631706429999170651706617067170681706929999170701707117072170731707429999170751707617077170781707929999170801708117082170831708429999170851708617087170881708929999170901709117092170931709429999170951709617097170981709929999171001710117102171031710429999171051710617107171081710929999171101711117112171131711429999171151711617117171181711929999171201712117122171231712429999171251712617127171281712929999171301713117132171331713429999171351713617137171381713929999171401714117142171431714429999171451714617147171481714929999171501715117152171531715429999171551715617157171581715929999171601716117162171631716429999171651716617167171681716929999171701717117172171731717429999171751717617177171781717929999171801718117182171831718429999171851718617187171881718929999171901719117192171931719429999171951719617197171981719929999172001720117202172031720429999172051720617207172081720929999172101721117212172131721429999172151721617217172181721929999172201722117222172231722429999172251722617227172281722929999172301723117232172331723429999172351723617237172381723929999172401724117242172431724429999172451724617247172481724929999172501725117252172531725429999172551725617257172581725929999172601726117262172631726429999172651726617267172681726929999172701727117272172731727429999172751727617277172781727929999172801728117282172831728429999172851728617287172881728929999172901729117292172931729429999172951729617297172981729929999173001730117302173031730429999173051730617307173081730929999173101731117312173131731429999173151731617317173181731929999173201732117322173231732429999173251732617327173281732929999173301733117332173331733429999173351733617337173381733929999173401734117342173431734429999173451734617347173481734929999173501735117352173531735429999173551735617357173581735929999173601736117362173631736429999173651736617367173681736929999173701737117372173731737429999173751737617377173781737929999173801738117382173831738429999173851738617387173881738929999173901739117392173931739429999173951739617397173981739929999174001740117402174031740429999174051740617407174081740929999174101741117412174131741429999174151741617417174181741929999174201742117422174231742429999174251742617427174281742929999174301743117432174331743429999174351743617437174381743929999174401744117442174431744429999174451744617447174481744929999174501745117452174531745429999174551745617457174581745929999174601746117462174631746429999174651746617467174681746929999174701747117472174731747429999174751747617477174781747929999174801748117482174831748429999174851748617487174881748929999174901749117492174931749429999174951749617497174981749929999175001750117502175031750429999175051750617507175081750929999175101751117512175131751429999175151751617517175181751929999175201752117522175231752429999175251752617527175281752929999175301753117532175331753429999175351753617537175381753929999175401754117542175431754429999175451754617547175481754929999175501755117552175531755429999175551755617557175581755929999175601756117562175631756429999175651756617567175681756929999175701757117572175731757429999175751757617577175781757929999175801758117582175831758429999175851758617587175881758929999175901759117592175931759429999175951759617597175981759929999176001760117602176031760429999176051760617607176081760929999176101761117612176131761429999176151761617617176181761929999176201762117622176231762429999176251762617627176281762929999176301763117632176331763429999176351763617637176381763929999176401764117642176431764429999176451764617647176481764929999176501765117652176531765429999176551765617657176581765929999176601766117662176631766429999176651766617667176681766929999176701767117672176731767429999176751767617677176781767929999176801768117682176831768429999176851768617687176881768929999176901769117692176931769429999176951769617697176981769929999177001770117702177031770429999177051770617707177081770929999177101771117712177131771429999177151771617717177181771929999177201772117722177231772429999177251772617727177281772929999177301773117732177331773429999177351773617737177381773929999177401774117742177431774429999177451774617747177481774929999177501775117752177531775429999177551775617757177581775929999177601776117762177631776429999177651776617767177681776929999177701777117772177731777429999177751777617777177781777929999177801778117782177831778429999177851778617787177881778929999177901779117792177931779429999177951779617797177981779929999178001780117802178031780429999178051780617807178081780929999178101781117812178131781429999178151781617817178181781929999178201782117822178231782429999178251782617827178281782929999178301783117832178331783429999178351783617837178381783929999178401784117842178431784429999178451784617847178481784929999178501785117852178531785429999178551785617857178581785929999178601786117862178631786429999178651786617867178681786929999178701787117872178731787429999178751787617877178781787929999178801788117882178831788429999178851788617887178881788929999178901789117892178931789429999178951789617897178981789929999179001790117902179031790429999179051790617907179081790929999179101791117912179131791429999179151791617917179181791929999179201792117922179231792429999179251792617927179281792929999179301793117932179331793429999179351793617937179381793929999179401794117942179431794429999179451794617947179481794929999179501795117952179531795429999179551795617957179581795929999179601796117962179631796429999179651796617967179681796929999179701797117972179731797429999179751797617977179781797929999179801798117982179831798429999179851798617987179881798929999179901799117992179931799429999179951799617997179981799929999180001800118002180031800429999180051800618007180081800929999180101801118012180131801429999180151801618017180181801929999180201802118022180231802429999180251802618027180281802929999180301803118032180331803429999180351803618037180381803929999180401804118042180431804429999180451804618047180481804929999180501805118052180531805429999180551805618057180581805929999180601806118062180631806429999180651806618067180681806929999180701807118072180731807429999180751807618077180781807929999180801808118082180831808429999180851808618087180881808929999180901809118092180931809429999180951809618097180981809929999181001810118102181031810429999181051810618107181081810929999181101811118112181131811429999181151811618117181181811929999181201812118122181231812429999181251812618127181281812929999181301813118132181331813429999181351813618137181381813929999181401814118142181431814429999181451814618147181481814929999181501815118152181531815429999181551815618157181581815929999181601816118162181631816429999181651816618167181681816929999181701817118172181731817429999181751817618177181781817929999181801818118182181831818429999181851818618187181881818929999181901819118192181931819429999181951819618197181981819929999182001820118202182031820429999182051820618207182081820929999182101821118212182131821429999182151821618217182181821929999182201822118222182231822429999182251822618227182281822929999182301823118232182331823429999182351823618237182381823929999182401824118242182431824429999182451824618247182481824929999182501825118252182531825429999182551825618257182581825929999182601826118262182631826429999182651826618267182681826929999182701827118272182731827429999182751827618277182781827929999182801828118282182831828429999182851828618287182881828929999182901829118292182931829429999182951829618297182981829929999183001830118302183031830429999183051830618307183081830929999183101831118312183131831429999183151831618317183181831929999183201832118322183231832429999183251832618327183281832929999183301833118332183331833429999183351833618337183381833929999183401834118342183431834429999183451834618347183481834929999183501835118352183531835429999183551835618357183581835929999183601836118362183631836429999183651836618367183681836929999183701837118372183731837429999183751837618377183781837929999183801838118382183831838429999183851838618387183881838929999183901839118392183931839429999183951839618397183981839929999184001840118402184031840429999184051840618407184081840929999184101841118412184131841429999184151841618417184181841929999184201842118422184231842429999184251842618427184281842929999184301843118432184331843429999184351843618437184381843929999184401844118442184431844429999184451844618447184481844929999184501845118452184531845429999184551845618457184581845929999184601846118462184631846429999184651846618467184681846929999184701847118472184731847429999184751847618477184781847929999184801848118482184831848429999184851848618487184881848929999184901849118492184931849429999184951849618497184981849929999185001850118502185031850429999185051850618507185081850929999185101851118512185131851429999185151851618517185181851929999185201852118522185231852429999185251852618527185281852929999185301853118532185331853429999185351853618537185381853929999185401854118542185431854429999185451854618547185481854929999185501855118552185531855429999185551855618557185581855929999185601856118562185631856429999185651856618567185681856929999185701857118572185731857429999185751857618577185781857929999185801858118582185831858429999185851858618587185881858929999185901859118592185931859429999185951859618597185981859929999186001860118602186031860429999186051860618607186081860929999186101861118612186131861429999186151861618617186181861929999186201862118622186231862429999186251862618627186281862929999186301863118632186331863429999186351863618637186381863929999186401864118642186431864429999186451864618647186481864929999186501865118652186531865429999186551865618657186581865929999186601866118662186631866429999186651866618667186681866929999186701867118672186731867429999186751867618677186781867929999186801868118682186831868429999186851868618687186881868929999186901869118692186931869429999186951869618697186981869929999187001870118702187031870429999187051870618707187081870929999187101871118712187131871429999187151871618717187181871929999187201872118722187231872429999187251872618727187281872929999187301873118732187331873429999187351873618737187381873929999187401874118742187431874429999187451874618747187481874929999187501875118752187531875429999187551875618757187581875929999187601876118762187631876429999187651876618767187681876929999187701877118772187731877429999187751877618777187781877929999187801878118782187831878429999187851878618787187881878929999187901879118792187931879429999187951879618797187981879929999188001880118802188031880429999188051880618807188081880929999188101881118812188131881429999188151881618817188181881929999188201882118822188231882429999188251882618827188281882929999188301883118832188331883429999188351883618837188381883929999188401884118842188431884429999188451884618847188481884929999188501885118852188531885429999188551885618857188581885929999188601886118862188631886429999188651886618867188681886929999188701887118872188731887429999188751887618877188781887929999188801888118882188831888429999188851888618887188881888929999188901889118892188931889429999188951889618897188981889929999189001890118902189031890429999189051890618907189081890929999189101891118912189131891429999189151891618917189181891929999189201892118922189231892429999189251892618927189281892929999189301893118932189331893429999189351893618937189381893929999189401894118942189431894429999189451894618947189481894929999189501895118952189531895429999189551895618957189581895929999189601896118962189631896429999189651896618967189681896929999189701897118972189731897429999189751897618977189781897929999189801898118982189831898429999189851898618987189881898929999189901899118992189931899429999189951899618997189981899929999190001900119002190031900429999190051900619007190081900929999190101901119012190131901429999190151901619017190181901929999190201902119022190231902429999190251902619027190281902929999190301903119032190331903429999190351903619037190381903929999190401904119042190431904429999190451904619047190481904929999190501905119052190531905429999190551905619057190581905929999190601906119062190631906429999190651906619067190681906929999190701907119072190731907429999190751907619077190781907929999190801908119082190831908429999190851908619087190881908929999190901909119092190931909429999190951909619097190981909929999191001910119102191031910429999191051910619107191081910929999191101911119112191131911429999191151911619117191181911929999191201912119122191231912429999191251912619127191281912929999191301913119132191331913429999191351913619137191381913929999191401914119142191431914429999191451914619147191481914929999191501915119152191531915429999191551915619157191581915929999191601916119162191631916429999191651916619167191681916929999191701917119172191731917429999191751917619177191781917929999191801918119182191831918429999191851918619187191881918929999191901919119192191931919429999191951919619197191981919929999192001920119202192031920429999192051920619207192081920929999192101921119212192131921429999192151921619217192181921929999192201922119222192231922429999192251922619227192281922929999192301923119232192331923429999192351923619237192381923929999192401924119242192431924429999192451924619247192481924929999192501925119252192531925429999192551925619257192581925929999192601926119262192631926429999192651926619267192681926929999192701927119272192731927429999192751927619277192781927929999192801928119282192831928429999192851928619287192881928929999192901929119292192931929429999192951929619297192981929929999193001930119302193031930429999193051930619307193081930929999193101931119312193131931429999193151931619317193181931929999193201932119322193231932429999193251932619327193281932929999193301933119332193331933429999193351933619337193381933929999193401934119342193431934429999193451934619347193481934929999193501935119352193531935429999193551935619357193581935929999193601936119362193631936429999193651936619367193681936929999193701937119372193731937429999193751937619377193781937929999193801938119382193831938429999193851938619387193881938929999193901939119392193931939429999193951939619397193981939929999194001940119402194031940429999194051940619407194081940929999194101941119412194131941429999194151941619417194181941929999194201942119422194231942429999194251942619427194281942929999194301943119432194331943429999194351943619437194381943929999194401944119442194431944429999194451944619447194481944929999194501945119452194531945429999194551945619457194581945929999194601946119462194631946429999194651946619467194681946929999194701947119472194731947429999194751947619477194781947929999194801948119482194831948429999194851948619487194881948929999194901949119492194931949429999194951949619497194981949929999195001950119502195031950429999195051950619507195081950929999195101951119512195131951429999195151951619517195181951929999195201952119522195231952429999195251952619527195281952929999195301953119532195331953429999195351953619537195381953929999195401954119542195431954429999195451954619547195481954929999195501955119552195531955429999195551955619557195581955929999195601956119562195631956429999195651956619567195681956929999195701957119572195731957429999195751957619577195781957929999195801958119582195831958429999195851958619587195881958929999195901959119592195931959429999195951959619597195981959929999196001960119602196031960429999196051960619607196081960929999196101961119612196131961429999196151961619617196181961929999196201962119622196231962429999196251962619627196281962929999196301963119632196331963429999196351963619637196381963929999196401964119642196431964429999196451964619647196481964929999196501965119652196531965429999196551965619657196581965929999196601966119662196631966429999196651966619667196681966929999196701967119672196731967429999196751967619677196781967929999196801968119682196831968429999196851968619687196881968929999196901969119692196931969429999196951969619697196981969929999197001970119702197031970429999197051970619707197081970929999197101971119712197131971429999197151971619717197181971929999197201972119722197231972429999197251972619727197281972929999197301973119732197331973429999197351973619737197381973929999197401974119742197431974429999197451974619747197481974929999197501975119752197531975429999197551975619757197581975929999197601976119762197631976429999197651976619767197681976929999197701977119772197731977429999197751977619777197781977929999197801978119782197831978429999197851978619787197881978929999197901979119792197931979429999197951979619797197981979929999198001980119802198031980429999198051980619807198081980929999198101981119812198131981429999198151981619817198181981929999198201982119822198231982429999198251982619827198281982929999198301983119832198331983429999198351983619837198381983929999198401984119842198431984429999198451984619847198481984929999198501985119852198531985429999198551985619857198581985929999198601986119862198631986429999198651986619867198681986929999198701987119872198731987429999198751987619877198781987929999198801988119882198831988429999198851988619887198881988929999198901989119892198931989429999198951989619897198981989929999199001990119902199031990429999199051990619907199081990929999199101991119912199131991429999199151991619917199181991929999199201992119922199231992429999199251992619927199281992929999199301993119932199331993429999199351993619937199381993929999199401994119942199431994429999199451994619947199481994929999199501995119952199531995429999199551995619957199581995929999199601996119962199631996429999199651996619967199681996929999199701997119972199731997429999199751997619977199781997929999199801998119982199831998429999199851998619987199881998929999199901999119992199931999429999199951999619997199981999929999200002000120002200032000429999200052000620007200082000929999200102001120012200132001429999200152001620017200182001929999200202002120022200232002429999200252002620027200282002929999200302003120032200332003429999200352003620037200382003929999200402004120042200432004429999200452004620047200482004929999200502005120052200532005429999200552005620057200582005929999200602006120062200632006429999200652006620067200682006929999200702007120072200732007429999200752007620077200782007929999200802008120082200832008429999200852008620087200882008929999200902009120092200932009429999200952009620097200982009929999201002010120102201032010429999201052010620107201082010929999201102011120112201132011429999201152011620117201182011929999201202012120122201232012429999201252012620127201282012929999201302013120132201332013429999201352013620137201382013929999201402014120142201432014429999201452014620147201482014929999201502015120152201532015429999201552015620157201582015929999201602016120162201632016429999201652016620167201682016929999201702017120172201732017429999201752017620177201782017929999201802018120182201832018429999201852018620187201882018929999201902019120192201932019429999201952019620197201982019929999202002020120202202032020429999202052020620207202082020929999202102021120212202132021429999202152021620217202182021929999202202022120222202232022429999202252022620227202282022929999202302023120232202332023429999202352023620237202382023929999202402024120242202432024429999202452024620247202482024929999202502025120252202532025429999202552025620257202582025929999202602026120262202632026429999202652026620267202682026929999202702027120272202732027429999202752027620277202782027929999202802028120282202832028429999202852028620287202882028929999202902029120292202932029429999202952029620297202982029929999203002030120302203032030429999203052030620307203082030929999203102031120312203132031429999203152031620317203182031929999203202032120322203232032429999203252032620327203282032929999203302033120332203332033429999203352033620337203382033929999203402034120342203432034429999203452034620347203482034929999203502035120352203532035429999203552035620357203582035929999203602036120362203632036429999203652036620367203682036929999203702037120372203732037429999203752037620377203782037929999203802038120382203832038429999203852038620387203882038929999203902039120392203932039429999203952039620397203982039929999204002040120402204032040429999204052040620407204082040929999204102041120412204132041429999204152041620417204182041929999204202042120422204232042429999204252042620427204282042929999204302043120432204332043429999204352043620437204382043929999204402044120442204432044429999204452044620447204482044929999204502045120452204532045429999204552045620457204582045929999204602046120462204632046429999204652046620467204682046929999204702047120472204732047429999204752047620477204782047929999204802048120482204832048429999204852048620487204882048929999204902049120492204932049429999204952049620497204982049929999205002050120502205032050429999205052050620507205082050929999205102051120512205132051429999205152051620517205182051929999205202052120522205232052429999205252052620527205282052929999205302053120532205332053429999205352053620537205382053929999205402054120542205432054429999205452054620547205482054929999205502055120552205532055429999205552055620557205582055929999205602056120562205632056429999205652056620567205682056929999205702057120572205732057429999205752057620577205782057929999205802058120582205832058429999205852058620587205882058929999205902059120592205932059429999205952059620597205982059929999206002060120602206032060429999206052060620607206082060929999206102061120612206132061429999206152061620617206182061929999206202062120622206232062429999206252062620627206282062929999206302063120632206332063429999206352063620637206382063929999206402064120642206432064429999206452064620647206482064929999206502065120652206532065429999206552065620657206582065929999206602066120662206632066429999206652066620667206682066929999206702067120672206732067429999206752067620677206782067929999206802068120682206832068429999206852068620687206882068929999206902069120692206932069429999206952069620697206982069929999207002070120702207032070429999207052070620707207082070929999207102071120712207132071429999207152071620717207182071929999207202072120722207232072429999207252072620727207282072929999207302073120732207332073429999207352073620737207382073929999207402074120742207432074429999207452074620747207482074929999207502075120752207532075429999207552075620757207582075929999207602076120762207632076429999207652076620767207682076929999207702077120772207732077429999207752077620777207782077929999207802078120782207832078429999207852078620787207882078929999207902079120792207932079429999207952079620797207982079929999208002080120802208032080429999208052080620807208082080929999208102081120812208132081429999208152081620817208182081929999208202082120822208232082429999208252082620827208282082929999208302083120832208332083429999208352083620837208382083929999208402084120842208432084429999208452084620847208482084929999208502085120852208532085429999208552085620857208582085929999208602086120862208632086429999208652086620867208682086929999208702087120872208732087429999208752087620877208782087929999208802088120882208832088429999208852088620887208882088929999208902089120892208932089429999208952089620897208982089929999209002090120902209032090429999209052090620907209082090929999209102091120912209132091429999209152091620917209182091929999209202092120922209232092429999209252092620927209282092929999209302093120932209332093429999209352093620937209382093929999209402094120942209432094429999209452094620947209482094929999209502095120952209532095429999209552095620957209582095929999209602096120962209632096429999209652096620967209682096929999209702097120972209732097429999209752097620977209782097929999209802098120982209832098429999209852098620987209882098929999209902099120992209932099429999209952099620997209982099929999210002100121002210032100429999210052100621007210082100929999210102101121012210132101429999210152101621017210182101929999210202102121022210232102429999210252102621027210282102929999210302103121032210332103429999210352103621037210382103929999210402104121042210432104429999210452104621047210482104929999210502105121052210532105429999210552105621057210582105929999210602106121062210632106429999210652106621067210682106929999210702107121072210732107429999210752107621077210782107929999210802108121082210832108429999210852108621087210882108929999210902109121092210932109429999210952109621097210982109929999211002110121102211032110429999211052110621107211082110929999211102111121112211132111429999211152111621117211182111929999211202112121122211232112429999211252112621127211282112929999211302113121132211332113429999211352113621137211382113929999211402114121142211432114429999211452114621147211482114929999211502115121152211532115429999211552115621157211582115929999211602116121162211632116429999211652116621167211682116929999211702117121172211732117429999211752117621177211782117929999211802118121182211832118429999211852118621187211882118929999211902119121192211932119429999211952119621197211982119929999212002120121202212032120429999212052120621207212082120929999212102121121212212132121429999212152121621217212182121929999212202122121222212232122429999212252122621227212282122929999212302123121232212332123429999212352123621237212382123929999212402124121242212432124429999212452124621247212482124929999212502125121252212532125429999212552125621257212582125929999212602126121262212632126429999212652126621267212682126929999212702127121272212732127429999212752127621277212782127929999212802128121282212832128429999212852128621287212882128929999212902129121292212932129429999212952129621297212982129929999213002130121302213032130429999213052130621307213082130929999213102131121312213132131429999213152131621317213182131929999213202132121322213232132429999213252132621327213282132929999213302133121332213332133429999213352133621337213382133929999213402134121342213432134429999213452134621347213482134929999213502135121352213532135429999213552135621357213582135929999213602136121362213632136429999213652136621367213682136929999213702137121372213732137429999213752137621377213782137929999213802138121382213832138429999213852138621387213882138929999213902139121392213932139429999213952139621397213982139929999214002140121402214032140429999214052140621407214082140929999214102141121412214132141429999214152141621417214182141929999214202142121422214232142429999214252142621427214282142929999214302143121432214332143429999214352143621437214382143929999214402144121442214432144429999214452144621447214482144929999214502145121452214532145429999214552145621457214582145929999214602146121462214632146429999214652146621467214682146929999214702147121472214732147429999214752147621477214782147929999214802148121482214832148429999214852148621487214882148929999214902149121492214932149429999214952149621497214982149929999215002150121502215032150429999215052150621507215082150929999215102151121512215132151429999215152151621517215182151929999215202152121522215232152429999215252152621527215282152929999215302153121532215332153429999215352153621537215382153929999215402154121542215432154429999215452154621547215482154929999215502155121552215532155429999215552155621557215582155929999215602156121562215632156429999215652156621567215682156929999215702157121572215732157429999215752157621577215782157929999215802158121582215832158429999215852158621587215882158929999215902159121592215932159429999215952159621597215982159929999216002160121602216032160429999216052160621607216082160929999216102161121612216132161429999216152161621617216182161929999216202162121622216232162429999216252162621627216282162929999216302163121632216332163429999216352163621637216382163929999216402164121642216432164429999216452164621647216482164929999216502165121652216532165429999216552165621657216582165929999216602166121662216632166429999216652166621667216682166929999216702167121672216732167429999216752167621677216782167929999216802168121682216832168429999216852168621687216882168929999216902169121692216932169429999216952169621697216982169929999217002170121702217032170429999217052170621707217082170929999217102171121712217132171429999217152171621717217182171929999217202172121722217232172429999217252172621727217282172929999217302173121732217332173429999217352173621737217382173929999217402174121742217432174429999217452174621747217482174929999217502175121752217532175429999217552175621757217582175929999217602176121762217632176429999217652176621767217682176929999217702177121772217732177429999217752177621777217782177929999217802178121782217832178429999217852178621787217882178929999217902179121792217932179429999217952179621797217982179929999218002180121802218032180429999218052180621807218082180929999218102181121812218132181429999218152181621817218182181929999218202182121822218232182429999218252182621827218282182929999218302183121832218332183429999218352183621837218382183929999218402184121842218432184429999218452184621847218482184929999218502185121852218532185429999218552185621857218582185929999218602186121862218632186429999218652186621867218682186929999218702187121872218732187429999218752187621877218782187929999218802188121882218832188429999218852188621887218882188929999218902189121892218932189429999218952189621897218982189929999219002190121902219032190429999219052190621907219082190929999219102191121912219132191429999219152191621917219182191929999219202192121922219232192429999219252192621927219282192929999219302193121932219332193429999219352193621937219382193929999219402194121942219432194429999219452194621947219482194929999219502195121952219532195429999219552195621957219582195929999219602196121962219632196429999219652196621967219682196929999219702197121972219732197429999219752197621977219782197929999219802198121982219832198429999219852198621987219882198929999219902199121992219932199429999219952199621997219982199929999220002200122002220032200429999220052200622007220082200929999220102201122012220132201429999220152201622017220182201929999220202202122022220232202429999220252202622027220282202929999220302203122032220332203429999220352203622037220382203929999220402204122042220432204429999220452204622047220482204929999220502205122052220532205429999220552205622057220582205929999220602206122062220632206429999220652206622067220682206929999220702207122072220732207429999220752207622077220782207929999220802208122082220832208429999220852208622087220882208929999220902209122092220932209429999220952209622097220982209929999221002210122102221032210429999221052210622107221082210929999221102211122112221132211429999221152211622117221182211929999221202212122122221232212429999221252212622127221282212929999221302213122132221332213429999221352213622137221382213929999221402214122142221432214429999221452214622147221482214929999221502215122152221532215429999221552215622157221582215929999221602216122162221632216429999221652216622167221682216929999221702217122172221732217429999221752217622177221782217929999221802218122182221832218429999221852218622187221882218929999221902219122192221932219429999221952219622197221982219929999222002220122202222032220429999222052220622207222082220929999222102221122212222132221429999222152221622217222182221929999222202222122222222232222429999222252222622227222282222929999222302223122232222332223429999222352223622237222382223929999222402224122242222432224429999222452224622247222482224929999222502225122252222532225429999222552225622257222582225929999222602226122262222632226429999222652226622267222682226929999222702227122272222732227429999222752227622277222782227929999222802228122282222832228429999222852228622287222882228929999222902229122292222932229429999222952229622297222982229929999223002230122302223032230429999223052230622307223082230929999223102231122312223132231429999223152231622317223182231929999223202232122322223232232429999223252232622327223282232929999223302233122332223332233429999223352233622337223382233929999223402234122342223432234429999223452234622347223482234929999223502235122352223532235429999223552235622357223582235929999223602236122362223632236429999223652236622367223682236929999223702237122372223732237429999223752237622377223782237929999223802238122382223832238429999223852238622387223882238929999223902239122392223932239429999223952239622397223982239929999224002240122402224032240429999224052240622407224082240929999224102241122412224132241429999224152241622417224182241929999224202242122422224232242429999224252242622427224282242929999224302243122432224332243429999224352243622437224382243929999224402244122442224432244429999224452244622447224482244929999224502245122452224532245429999224552245622457224582245929999224602246122462224632246429999224652246622467224682246929999224702247122472224732247429999224752247622477224782247929999224802248122482224832248429999224852248622487224882248929999224902249122492224932249429999224952249622497224982249929999225002250122502225032250429999225052250622507225082250929999225102251122512225132251429999225152251622517225182251929999225202252122522225232252429999225252252622527225282252929999225302253122532225332253429999225352253622537225382253929999225402254122542225432254429999225452254622547225482254929999225502255122552225532255429999225552255622557225582255929999225602256122562225632256429999225652256622567225682256929999225702257122572225732257429999225752257622577225782257929999225802258122582225832258429999225852258622587225882258929999225902259122592225932259429999225952259622597225982259929999226002260122602226032260429999226052260622607226082260929999226102261122612226132261429999226152261622617226182261929999226202262122622226232262429999226252262622627226282262929999226302263122632226332263429999226352263622637226382263929999226402264122642226432264429999226452264622647226482264929999226502265122652226532265429999226552265622657226582265929999226602266122662226632266429999226652266622667226682266929999226702267122672226732267429999226752267622677226782267929999226802268122682226832268429999226852268622687226882268929999226902269122692226932269429999226952269622697226982269929999227002270122702227032270429999227052270622707227082270929999227102271122712227132271429999227152271622717227182271929999227202272122722227232272429999227252272622727227282272929999227302273122732227332273429999227352273622737227382273929999227402274122742227432274429999227452274622747227482274929999227502275122752227532275429999227552275622757227582275929999227602276122762227632276429999227652276622767227682276929999227702277122772227732277429999227752277622777227782277929999227802278122782227832278429999227852278622787227882278929999227902279122792227932279429999227952279622797227982279929999228002280122802228032280429999228052280622807228082280929999228102281122812228132281429999228152281622817228182281929999228202282122822228232282429999228252282622827228282282929999228302283122832228332283429999228352283622837228382283929999228402284122842228432284429999228452284622847228482284929999228502285122852228532285429999228552285622857228582285929999228602286122862228632286429999228652286622867228682286929999228702287122872228732287429999228752287622877228782287929999228802288122882228832288429999228852288622887228882288929999228902289122892228932289429999228952289622897228982289929999229002290122902229032290429999229052290622907229082290929999229102291122912229132291429999229152291622917229182291929999229202292122922229232292429999229252292622927229282292929999229302293122932229332293429999229352293622937229382293929999229402294122942229432294429999229452294622947229482294929999229502295122952229532295429999229552295622957229582295929999229602296122962229632296429999229652296622967229682296929999229702297122972229732297429999229752297622977229782297929999229802298122982229832298429999229852298622987229882298929999229902299122992229932299429999229952299622997229982299929999230002300123002230032300429999230052300623007230082300929999230102301123012230132301429999230152301623017230182301929999230202302123022230232302429999230252302623027230282302929999230302303123032230332303429999230352303623037230382303929999230402304123042230432304429999230452304623047230482304929999230502305123052230532305429999230552305623057230582305929999230602306123062230632306429999230652306623067230682306929999230702307123072230732307429999230752307623077230782307929999230802308123082230832308429999230852308623087230882308929999230902309123092230932309429999230952309623097230982309929999231002310123102231032310429999231052310623107231082310929999231102311123112231132311429999231152311623117231182311929999231202312123122231232312429999231252312623127231282312929999231302313123132231332313429999231352313623137231382313929999231402314123142231432314429999231452314623147231482314929999231502315123152231532315429999231552315623157231582315929999231602316123162231632316429999231652316623167231682316929999231702317123172231732317429999231752317623177231782317929999231802318123182231832318429999231852318623187231882318929999231902319123192231932319429999231952319623197231982319929999232002320123202232032320429999232052320623207232082320929999232102321123212232132321429999232152321623217232182321929999232202322123222232232322429999232252322623227232282322929999232302323123232232332323429999232352323623237232382323929999232402324123242232432324429999232452324623247232482324929999232502325123252232532325429999232552325623257232582325929999232602326123262232632326429999232652326623267232682326929999232702327123272232732327429999232752327623277232782327929999232802328123282232832328429999232852328623287232882328929999232902329123292232932329429999232952329623297232982329929999233002330123302233032330429999233052330623307233082330929999233102331123312233132331429999233152331623317233182331929999233202332123322233232332429999233252332623327233282332929999233302333123332233332333429999233352333623337233382333929999233402334123342233432334429999233452334623347233482334929999233502335123352233532335429999233552335623357233582335929999233602336123362233632336429999233652336623367233682336929999233702337123372233732337429999233752337623377233782337929999233802338123382233832338429999233852338623387233882338929999233902339123392233932339429999233952339623397233982339929999234002340123402234032340429999234052340623407234082340929999234102341123412234132341429999234152341623417234182341929999234202342123422234232342429999234252342623427234282342929999234302343123432234332343429999234352343623437234382343929999234402344123442234432344429999234452344623447234482344929999234502345123452234532345429999234552345623457234582345929999234602346123462234632346429999234652346623467234682346929999234702347123472234732347429999234752347623477234782347929999234802348123482234832348429999234852348623487234882348929999234902349123492234932349429999234952349623497234982349929999235002350123502235032350429999235052350623507235082350929999235102351123512235132351429999235152351623517235182351929999235202352123522235232352429999235252352623527235282352929999235302353123532235332353429999235352353623537235382353929999235402354123542235432354429999235452354623547235482354929999235502355123552235532355429999235552355623557235582355929999235602356123562235632356429999235652356623567235682356929999235702357123572235732357429999235752357623577235782357929999235802358123582235832358429999235852358623587235882358929999235902359123592235932359429999235952359623597235982359929999236002360123602236032360429999236052360623607236082360929999236102361123612236132361429999236152361623617236182361929999236202362123622236232362429999236252362623627236282362929999236302363123632236332363429999236352363623637236382363929999236402364123642236432364429999236452364623647236482364929999236502365123652236532365429999236552365623657236582365929999236602366123662236632366429999236652366623667236682366929999236702367123672236732367429999236752367623677236782367929999236802368123682236832368429999236852368623687236882368929999236902369123692236932369429999236952369623697236982369929999237002370123702237032370429999237052370623707237082370929999237102371123712237132371429999237152371623717237182371929999237202372123722237232372429999237252372623727237282372929999237302373123732237332373429999237352373623737237382373929999237402374123742237432374429999237452374623747237482374929999237502375123752237532375429999237552375623757237582375929999237602376123762237632376429999237652376623767237682376929999237702377123772237732377429999237752377623777237782377929999237802378123782237832378429999237852378623787237882378929999237902379123792237932379429999237952379623797237982379929999238002380123802238032380429999238052380623807238082380929999238102381123812238132381429999238152381623817238182381929999238202382123822238232382429999238252382623827238282382929999238302383123832238332383429999238352383623837238382383929999238402384123842238432384429999238452384623847238482384929999238502385123852238532385429999238552385623857238582385929999238602386123862238632386429999238652386623867238682386929999238702387123872238732387429999238752387623877238782387929999238802388123882238832388429999238852388623887238882388929999238902389123892238932389429999238952389623897238982389929999239002390123902239032390429999239052390623907239082390929999239102391123912239132391429999239152391623917239182391929999239202392123922239232392429999239252392623927239282392929999239302393123932239332393429999239352393623937239382393929999239402394123942239432394429999239452394623947239482394929999239502395123952239532395429999239552395623957239582395929999239602396123962239632396429999239652396623967239682396929999239702397123972239732397429999239752397623977239782397929999239802398123982239832398429999239852398623987239882398929999239902399123992239932399429999239952399623997239982399929999240002400124002240032400429999240052400624007240082400929999240102401124012240132401429999240152401624017240182401929999240202402124022240232402429999240252402624027240282402929999240302403124032240332403429999240352403624037240382403929999240402404124042240432404429999240452404624047240482404929999240502405124052240532405429999240552405624057240582405929999240602406124062240632406429999240652406624067240682406929999240702407124072240732407429999240752407624077240782407929999240802408124082240832408429999240852408624087240882408929999240902409124092240932409429999240952409624097240982409929999241002410124102241032410429999241052410624107241082410929999241102411124112241132411429999241152411624117241182411929999241202412124122241232412429999241252412624127241282412929999241302413124132241332413429999241352413624137241382413929999241402414124142241432414429999241452414624147241482414929999241502415124152241532415429999241552415624157241582415929999241602416124162241632416429999241652416624167241682416929999241702417124172241732417429999241752417624177241782417929999241802418124182241832418429999241852418624187241882418929999241902419124192241932419429999241952419624197241982419929999242002420124202242032420429999242052420624207242082420929999242102421124212242132421429999242152421624217242182421929999242202422124222242232422429999242252422624227242282422929999242302423124232242332423429999242352423624237242382423929999242402424124242242432424429999242452424624247242482424929999242502425124252242532425429999242552425624257242582425929999242602426124262242632426429999242652426624267242682426929999242702427124272242732427429999242752427624277242782427929999242802428124282242832428429999242852428624287242882428929999242902429124292242932429429999242952429624297242982429929999243002430124302243032430429999243052430624307243082430929999243102431124312243132431429999243152431624317243182431929999243202432124322243232432429999243252432624327243282432929999243302433124332243332433429999243352433624337243382433929999243402434124342243432434429999243452434624347243482434929999243502435124352243532435429999243552435624357243582435929999243602436124362243632436429999243652436624367243682436929999243702437124372243732437429999243752437624377243782437929999243802438124382243832438429999243852438624387243882438929999243902439124392243932439429999243952439624397243982439929999244002440124402244032440429999244052440624407244082440929999244102441124412244132441429999244152441624417244182441929999244202442124422244232442429999244252442624427244282442929999244302443124432244332443429999244352443624437244382443929999244402444124442244432444429999244452444624447244482444929999244502445124452244532445429999244552445624457244582445929999244602446124462244632446429999244652446624467244682446929999244702447124472244732447429999244752447624477244782447929999244802448124482244832448429999244852448624487244882448929999244902449124492244932449429999244952449624497244982449929999245002450124502245032450429999245052450624507245082450929999245102451124512245132451429999245152451624517245182451929999245202452124522245232452429999245252452624527245282452929999245302453124532245332453429999245352453624537245382453929999245402454124542245432454429999245452454624547245482454929999245502455124552245532455429999245552455624557245582455929999245602456124562245632456429999245652456624567245682456929999245702457124572245732457429999245752457624577245782457929999245802458124582245832458429999245852458624587245882458929999245902459124592245932459429999245952459624597245982459929999246002460124602246032460429999246052460624607246082460929999246102461124612246132461429999246152461624617246182461929999246202462124622246232462429999246252462624627246282462929999246302463124632246332463429999246352463624637246382463929999246402464124642246432464429999246452464624647246482464929999246502465124652246532465429999246552465624657246582465929999246602466124662246632466429999246652466624667246682466929999246702467124672246732467429999246752467624677246782467929999246802468124682246832468429999246852468624687246882468929999246902469124692246932469429999246952469624697246982469929999247002470124702247032470429999247052470624707247082470929999247102471124712247132471429999247152471624717247182471929999247202472124722247232472429999247252472624727247282472929999247302473124732247332473429999247352473624737247382473929999247402474124742247432474429999247452474624747247482474929999247502475124752247532475429999247552475624757247582475929999247602476124762247632476429999247652476624767247682476929999247702477124772247732477429999247752477624777247782477929999247802478124782247832478429999247852478624787247882478929999247902479124792247932479429999247952479624797247982479929999248002480124802248032480429999248052480624807248082480929999248102481124812248132481429999248152481624817248182481929999248202482124822248232482429999248252482624827248282482929999248302483124832248332483429999248352483624837248382483929999248402484124842248432484429999248452484624847248482484929999248502485124852248532485429999248552485624857248582485929999248602486124862248632486429999248652486624867248682486929999248702487124872248732487429999248752487624877248782487929999248802488124882248832488429999248852488624887248882488929999248902489124892248932489429999248952489624897248982489929999249002490124902249032490429999249052490624907249082490929999249102491124912249132491429999249152491624917249182491929999249202492124922249232492429999249252492624927249282492929999249302493124932249332493429999249352493624937249382493929999249402494124942249432494429999249452494624947249482494929999249502495124952249532495429999249552495624957249582495929999249602496124962249632496429999249652496624967249682496929999249702497124972249732497429999249752497624977249782497929999249802498124982249832498429999249852498624987249882498929999249902499124992249932499429999249952499624997249982499929999250002500125002250032500429999250052500625007250082500929999250102501125012250132501429999250152501625017250182501929999250202502125022250232502429999250252502625027250282502929999250302503125032250332503429999250352503625037250382503929999250402504125042250432504429999250452504625047250482504929999250502505125052250532505429999250552505625057250582505929999250602506125062250632506429999250652506625067250682506929999250702507125072250732507429999250752507625077250782507929999250802508125082250832508429999250852508625087250882508929999250902509125092250932509429999250952509625097250982509929999251002510125102251032510429999251052510625107251082510929999251102511125112251132511429999251152511625117251182511929999251202512125122251232512429999251252512625127251282512929999251302513125132251332513429999251352513625137251382513929999251402514125142251432514429999251452514625147251482514929999251502515125152251532515429999251552515625157251582515929999251602516125162251632516429999251652516625167251682516929999251702517125172251732517429999251752517625177251782517929999251802518125182251832518429999251852518625187251882518929999251902519125192251932519429999251952519625197251982519929999252002520125202252032520429999252052520625207252082520929999252102521125212252132521429999252152521625217252182521929999252202522125222252232522429999252252522625227252282522929999252302523125232252332523429999252352523625237252382523929999252402524125242252432524429999252452524625247252482524929999252502525125252252532525429999252552525625257252582525929999252602526125262252632526429999252652526625267252682526929999252702527125272252732527429999252752527625277252782527929999252802528125282252832528429999252852528625287252882528929999252902529125292252932529429999252952529625297252982529929999253002530125302253032530429999253052530625307253082530929999253102531125312253132531429999253152531625317253182531929999253202532125322253232532429999253252532625327253282532929999253302533125332253332533429999253352533625337253382533929999253402534125342253432534429999253452534625347253482534929999253502535125352253532535429999253552535625357253582535929999253602536125362253632536429999253652536625367253682536929999253702537125372253732537429999253752537625377253782537929999253802538125382253832538429999253852538625387253882538929999253902539125392253932539429999253952539625397253982539929999254002540125402254032540429999254052540625407254082540929999254102541125412254132541429999254152541625417254182541929999254202542125422254232542429999254252542625427254282542929999254302543125432254332543429999254352543625437254382543929999254402544125442254432544429999254452544625447254482544929999254502545125452254532545429999254552545625457254582545929999254602546125462254632546429999254652546625467254682546929999254702547125472254732547429999254752547625477254782547929999254802548125482254832548429999254852548625487254882548929999254902549125492254932549429999254952549625497254982549929999255002550125502255032550429999255052550625507255082550929999255102551125512255132551429999255152551625517255182551929999255202552125522255232552429999255252552625527255282552929999255302553125532255332553429999255352553625537255382553929999255402554125542255432554429999255452554625547255482554929999255502555125552255532555429999255552555625557255582555929999255602556125562255632556429999255652556625567255682556929999255702557125572255732557429999255752557625577255782557929999255802558125582255832558429999255852558625587255882558929999255902559125592255932559429999255952559625597255982559929999256002560125602256032560429999256052560625607256082560929999256102561125612256132561429999256152561625617256182561929999256202562125622256232562429999256252562625627256282562929999256302563125632256332563429999256352563625637256382563929999256402564125642256432564429999256452564625647256482564929999256502565125652256532565429999256552565625657256582565929999256602566125662256632566429999256652566625667256682566929999256702567125672256732567429999256752567625677256782567929999256802568125682256832568429999256852568625687256882568929999256902569125692256932569429999256952569625697256982569929999257002570125702257032570429999257052570625707257082570929999257102571125712257132571429999257152571625717257182571929999257202572125722257232572429999257252572625727257282572929999257302573125732257332573429999257352573625737257382573929999257402574125742257432574429999257452574625747257482574929999257502575125752257532575429999257552575625757257582575929999257602576125762257632576429999257652576625767257682576929999257702577125772257732577429999257752577625777257782577929999257802578125782257832578429999257852578625787257882578929999257902579125792257932579429999257952579625797257982579929999258002580125802258032580429999258052580625807258082580929999258102581125812258132581429999258152581625817258182581929999258202582125822258232582429999258252582625827258282582929999258302583125832258332583429999258352583625837258382583929999258402584125842258432584429999258452584625847258482584929999258502585125852258532585429999258552585625857258582585929999258602586125862258632586429999258652586625867258682586929999258702587125872258732587429999258752587625877258782587929999258802588125882258832588429999258852588625887258882588929999258902589125892258932589429999258952589625897258982589929999259002590125902259032590429999259052590625907259082590929999259102591125912259132591429999259152591625917259182591929999259202592125922259232592429999259252592625927259282592929999259302593125932259332593429999259352593625937259382593929999259402594125942259432594429999259452594625947259482594929999259502595125952259532595429999259552595625957259582595929999259602596125962259632596429999259652596625967259682596929999259702597125972259732597429999259752597625977259782597929999259802598125982259832598429999259852598625987259882598929999259902599125992259932599429999259952599625997259982599929999260002600126002260032600429999260052600626007260082600929999260102601126012260132601429999260152601626017260182601929999260202602126022260232602429999260252602626027260282602929999260302603126032260332603429999260352603626037260382603929999260402604126042260432604429999260452604626047260482604929999260502605126052260532605429999260552605626057260582605929999260602606126062260632606429999260652606626067260682606929999260702607126072260732607429999260752607626077260782607929999260802608126082260832608429999260852608626087260882608929999260902609126092260932609429999260952609626097260982609929999261002610126102261032610429999261052610626107261082610929999261102611126112261132611429999261152611626117261182611929999261202612126122261232612429999261252612626127261282612929999261302613126132261332613429999261352613626137261382613929999261402614126142261432614429999261452614626147261482614929999261502615126152261532615429999261552615626157261582615929999261602616126162261632616429999261652616626167261682616929999261702617126172261732617429999261752617626177261782617929999261802618126182261832618429999261852618626187261882618929999261902619126192261932619429999261952619626197261982619929999262002620126202262032620429999262052620626207262082620929999262102621126212262132621429999262152621626217262182621929999262202622126222262232622429999262252622626227262282622929999262302623126232262332623429999262352623626237262382623929999262402624126242262432624429999262452624626247262482624929999262502625126252262532625429999262552625626257262582625929999262602626126262262632626429999262652626626267262682626929999262702627126272262732627429999262752627626277262782627929999262802628126282262832628429999262852628626287262882628929999262902629126292262932629429999262952629626297262982629929999263002630126302263032630429999263052630626307263082630929999263102631126312263132631429999263152631626317263182631929999263202632126322263232632429999263252632626327263282632929999263302633126332263332633429999263352633626337263382633929999263402634126342263432634429999263452634626347263482634929999263502635126352263532635429999263552635626357263582635929999263602636126362263632636429999263652636626367263682636929999263702637126372263732637429999263752637626377263782637929999263802638126382263832638429999263852638626387263882638929999263902639126392263932639429999263952639626397263982639929999264002640126402264032640429999264052640626407264082640929999264102641126412264132641429999264152641626417264182641929999264202642126422264232642429999264252642626427264282642929999264302643126432264332643429999264352643626437264382643929999264402644126442264432644429999264452644626447264482644929999264502645126452264532645429999264552645626457264582645929999264602646126462264632646429999264652646626467264682646929999264702647126472264732647429999264752647626477264782647929999264802648126482264832648429999264852648626487264882648929999264902649126492264932649429999264952649626497264982649929999265002650126502265032650429999265052650626507265082650929999265102651126512265132651429999265152651626517265182651929999265202652126522265232652429999265252652626527265282652929999265302653126532265332653429999265352653626537265382653929999265402654126542265432654429999265452654626547265482654929999265502655126552265532655429999265552655626557265582655929999265602656126562265632656429999265652656626567265682656929999265702657126572265732657429999265752657626577265782657929999265802658126582265832658429999265852658626587265882658929999265902659126592265932659429999265952659626597265982659929999266002660126602266032660429999266052660626607266082660929999266102661126612266132661429999266152661626617266182661929999266202662126622266232662429999266252662626627266282662929999266302663126632266332663429999266352663626637266382663929999266402664126642266432664429999266452664626647266482664929999266502665126652266532665429999266552665626657266582665929999266602666126662266632666429999266652666626667266682666929999266702667126672266732667429999266752667626677266782667929999266802668126682266832668429999266852668626687266882668929999266902669126692266932669429999266952669626697266982669929999267002670126702267032670429999267052670626707267082670929999267102671126712267132671429999267152671626717267182671929999267202672126722267232672429999267252672626727267282672929999267302673126732267332673429999267352673626737267382673929999267402674126742267432674429999267452674626747267482674929999267502675126752267532675429999267552675626757267582675929999267602676126762267632676429999267652676626767267682676929999267702677126772267732677429999267752677626777267782677929999267802678126782267832678429999267852678626787267882678929999267902679126792267932679429999267952679626797267982679929999268002680126802268032680429999268052680626807268082680929999268102681126812268132681429999268152681626817268182681929999268202682126822268232682429999268252682626827268282682929999268302683126832268332683429999268352683626837268382683929999268402684126842268432684429999268452684626847268482684929999268502685126852268532685429999268552685626857268582685929999268602686126862268632686429999268652686626867268682686929999268702687126872268732687429999268752687626877268782687929999268802688126882268832688429999268852688626887268882688929999268902689126892268932689429999268952689626897268982689929999269002690126902269032690429999269052690626907269082690929999269102691126912269132691429999269152691626917269182691929999269202692126922269232692429999269252692626927269282692929999269302693126932269332693429999269352693626937269382693929999269402694126942269432694429999269452694626947269482694929999269502695126952269532695429999269552695626957269582695929999269602696126962269632696429999269652696626967269682696929999269702697126972269732697429999269752697626977269782697929999269802698126982269832698429999269852698626987269882698929999269902699126992269932699429999269952699626997269982699929999270002700127002270032700429999270052700627007270082700929999270102701127012270132701429999270152701627017270182701929999270202702127022270232702429999270252702627027270282702929999270302703127032270332703429999270352703627037270382703929999270402704127042270432704429999270452704627047270482704929999270502705127052270532705429999270552705627057270582705929999270602706127062270632706429999270652706627067270682706929999270702707127072270732707429999270752707627077270782707929999270802708127082270832708429999270852708627087270882708929999270902709127092270932709429999270952709627097270982709929999271002710127102271032710429999271052710627107271082710929999271102711127112271132711429999271152711627117271182711929999271202712127122271232712429999271252712627127271282712929999271302713127132271332713429999271352713627137271382713929999271402714127142271432714429999271452714627147271482714929999271502715127152271532715429999271552715627157271582715929999271602716127162271632716429999271652716627167271682716929999271702717127172271732717429999271752717627177271782717929999271802718127182271832718429999271852718627187271882718929999271902719127192271932719429999271952719627197271982719929999272002720127202272032720429999272052720627207272082720929999272102721127212272132721429999272152721627217272182721929999272202722127222272232722429999272252722627227272282722929999272302723127232272332723429999272352723627237272382723929999272402724127242272432724429999272452724627247272482724929999272502725127252272532725429999272552725627257272582725929999272602726127262272632726429999272652726627267272682726929999272702727127272272732727429999272752727627277272782727929999272802728127282272832728429999272852728627287272882728929999272902729127292272932729429999272952729627297272982729929999273002730127302273032730429999273052730627307273082730929999273102731127312273132731429999273152731627317273182731929999273202732127322273232732429999273252732627327273282732929999273302733127332273332733429999273352733627337273382733929999273402734127342273432734429999273452734627347273482734929999273502735127352273532735429999273552735627357273582735929999273602736127362273632736429999273652736627367273682736929999273702737127372273732737429999273752737627377273782737929999273802738127382273832738429999273852738627387273882738929999273902739127392273932739429999273952739627397273982739929999274002740127402274032740429999274052740627407274082740929999274102741127412274132741429999274152741627417274182741929999274202742127422274232742429999274252742627427274282742929999274302743127432274332743429999274352743627437274382743929999274402744127442274432744429999274452744627447274482744929999274502745127452274532745429999274552745627457274582745929999274602746127462274632746429999274652746627467274682746929999274702747127472274732747429999274752747627477274782747929999274802748127482274832748429999274852748627487274882748929999274902749127492274932749429999274952749627497274982749929999275002750127502275032750429999275052750627507275082750929999275102751127512275132751429999275152751627517275182751929999275202752127522275232752429999275252752627527275282752929999275302753127532275332753429999275352753627537275382753929999275402754127542275432754429999275452754627547275482754929999275502755127552275532755429999275552755627557275582755929999275602756127562275632756429999275652756627567275682756929999275702757127572275732757429999275752757627577275782757929999275802758127582275832758429999275852758627587275882758929999275902759127592275932759429999275952759627597275982759929999276002760127602276032760429999276052760627607276082760929999276102761127612276132761429999276152761627617276182761929999276202762127622276232762429999276252762627627276282762929999276302763127632276332763429999276352763627637276382763929999276402764127642276432764429999276452764627647276482764929999276502765127652276532765429999276552765627657276582765929999276602766127662276632766429999276652766627667276682766929999276702767127672276732767429999276752767627677276782767929999276802768127682276832768429999276852768627687276882768929999276902769127692276932769429999276952769627697276982769929999277002770127702277032770429999277052770627707277082770929999277102771127712277132771429999277152771627717277182771929999277202772127722277232772429999277252772627727277282772929999277302773127732277332773429999277352773627737277382773929999277402774127742277432774429999277452774627747277482774929999277502775127752277532775429999277552775627757277582775929999277602776127762277632776429999277652776627767277682776929999277702777127772277732777429999277752777627777277782777929999277802778127782277832778429999277852778627787277882778929999277902779127792277932779429999277952779627797277982779929999278002780127802278032780429999278052780627807278082780929999278102781127812278132781429999278152781627817278182781929999278202782127822278232782429999278252782627827278282782929999278302783127832278332783429999278352783627837278382783929999278402784127842278432784429999278452784627847278482784929999278502785127852278532785429999278552785627857278582785929999278602786127862278632786429999278652786627867278682786929999278702787127872278732787429999278752787627877278782787929999278802788127882278832788429999278852788627887278882788929999278902789127892278932789429999278952789627897278982789929999279002790127902279032790429999279052790627907279082790929999279102791127912279132791429999279152791627917279182791929999279202792127922279232792429999279252792627927279282792929999279302793127932279332793429999279352793627937279382793929999279402794127942279432794429999279452794627947279482794929999279502795127952279532795429999279552795627957279582795929999279602796127962279632796429999279652796627967279682796929999279702797127972279732797429999279752797627977279782797929999279802798127982279832798429999279852798627987279882798929999279902799127992279932799429999279952799627997279982799929999280002800128002280032800429999280052800628007280082800929999280102801128012280132801429999280152801628017280182801929999280202802128022280232802429999280252802628027280282802929999280302803128032280332803429999280352803628037280382803929999280402804128042280432804429999280452804628047280482804929999280502805128052280532805429999280552805628057280582805929999280602806128062280632806429999280652806628067280682806929999280702807128072280732807429999280752807628077280782807929999280802808128082280832808429999280852808628087280882808929999280902809128092280932809429999280952809628097280982809929999281002810128102281032810429999281052810628107281082810929999281102811128112281132811429999281152811628117281182811929999281202812128122281232812429999281252812628127281282812929999281302813128132281332813429999281352813628137281382813929999281402814128142281432814429999281452814628147281482814929999281502815128152281532815429999281552815628157281582815929999281602816128162281632816429999281652816628167281682816929999281702817128172281732817429999281752817628177281782817929999281802818128182281832818429999281852818628187281882818929999281902819128192281932819429999281952819628197281982819929999282002820128202282032820429999282052820628207282082820929999282102821128212282132821429999282152821628217282182821929999282202822128222282232822429999282252822628227282282822929999282302823128232282332823429999282352823628237282382823929999282402824128242282432824429999282452824628247282482824929999282502825128252282532825429999282552825628257282582825929999282602826128262282632826429999282652826628267282682826929999282702827128272282732827429999282752827628277282782827929999282802828128282282832828429999282852828628287282882828929999282902829128292282932829429999282952829628297282982829929999283002830128302283032830429999283052830628307283082830929999283102831128312283132831429999283152831628317283182831929999283202832128322283232832429999283252832628327283282832929999283302833128332283332833429999283352833628337283382833929999283402834128342283432834429999283452834628347283482834929999283502835128352283532835429999283552835628357283582835929999283602836128362283632836429999283652836628367283682836929999283702837128372283732837429999283752837628377283782837929999283802838128382283832838429999283852838628387283882838929999283902839128392283932839429999283952839628397283982839929999284002840128402284032840429999284052840628407284082840929999284102841128412284132841429999284152841628417284182841929999284202842128422284232842429999284252842628427284282842929999284302843128432284332843429999284352843628437284382843929999284402844128442284432844429999284452844628447284482844929999284502845128452284532845429999284552845628457284582845929999284602846128462284632846429999284652846628467284682846929999284702847128472284732847429999284752847628477284782847929999284802848128482284832848429999284852848628487284882848929999284902849128492284932849429999284952849628497284982849929999285002850128502285032850429999285052850628507285082850929999285102851128512285132851429999285152851628517285182851929999285202852128522285232852429999285252852628527285282852929999285302853128532285332853429999285352853628537285382853929999285402854128542285432854429999285452854628547285482854929999285502855128552285532855429999285552855628557285582855929999285602856128562285632856429999285652856628567285682856929999285702857128572285732857429999285752857628577285782857929999285802858128582285832858429999285852858628587285882858929999285902859128592285932859429999285952859628597285982859929999286002860128602286032860429999286052860628607286082860929999286102861128612286132861429999286152861628617286182861929999286202862128622286232862429999286252862628627286282862929999286302863128632286332863429999286352863628637286382863929999286402864128642286432864429999286452864628647286482864929999286502865128652286532865429999286552865628657286582865929999286602866128662286632866429999286652866628667286682866929999286702867128672286732867429999286752867628677286782867929999286802868128682286832868429999286852868628687286882868929999286902869128692286932869429999286952869628697286982869929999287002870128702287032870429999287052870628707287082870929999287102871128712287132871429999287152871628717287182871929999287202872128722287232872429999287252872628727287282872929999287302873128732287332873429999287352873628737287382873929999287402874128742287432874429999287452874628747287482874929999287502875128752287532875429999287552875628757287582875929999287602876128762287632876429999287652876628767287682876929999287702877128772287732877429999287752877628777287782877929999287802878128782287832878429999287852878628787287882878929999287902879128792287932879429999287952879628797287982879929999288002880128802288032880429999288052880628807288082880929999288102881128812288132881429999288152881628817288182881929999288202882128822288232882429999288252882628827288282882929999288302883128832288332883429999288352883628837288382883929999288402884128842288432884429999288452884628847288482884929999288502885128852288532885429999288552885628857288582885929999288602886128862288632886429999288652886628867288682886929999288702887128872288732887429999288752887628877288782887929999288802888128882288832888429999288852888628887288882888929999288902889128892288932889429999288952889628897288982889929999289002890128902289032890429999289052890628907289082890929999289102891128912289132891429999289152891628917289182891929999289202892128922289232892429999289252892628927289282892929999289302893128932289332893429999289352893628937289382893929999289402894128942289432894429999289452894628947289482894929999289502895128952289532895429999289552895628957289582895929999289602896128962289632896429999289652896628967289682896929999289702897128972289732897429999289752897628977289782897929999289802898128982289832898429999289852898628987289882898929999289902899128992289932899429999289952899628997289982899929999290002900129002290032900429999290052900629007290082900929999290102901129012290132901429999290152901629017290182901929999290202902129022290232902429999290252902629027290282902929999290302903129032290332903429999290352903629037290382903929999290402904129042290432904429999290452904629047290482904929999290502905129052290532905429999290552905629057290582905929999290602906129062290632906429999290652906629067290682906929999290702907129072290732907429999290752907629077290782907929999290802908129082290832908429999290852908629087290882908929999290902909129092290932909429999290952909629097290982909929999291002910129102291032910429999291052910629107291082910929999291102911129112291132911429999291152911629117291182911929999291202912129122291232912429999291252912629127291282912929999291302913129132291332913429999291352913629137291382913929999291402914129142291432914429999291452914629147291482914929999291502915129152291532915429999291552915629157291582915929999291602916129162291632916429999291652916629167291682916929999291702917129172291732917429999291752917629177291782917929999291802918129182291832918429999291852918629187291882918929999291902919129192291932919429999291952919629197291982919929999292002920129202292032920429999292052920629207292082920929999292102921129212292132921429999292152921629217292182921929999292202922129222292232922429999292252922629227292282922929999292302923129232292332923429999292352923629237292382923929999292402924129242292432924429999292452924629247292482924929999292502925129252292532925429999292552925629257292582925929999292602926129262292632926429999292652926629267292682926929999292702927129272292732927429999292752927629277292782927929999292802928129282292832928429999292852928629287292882928929999292902929129292292932929429999292952929629297292982929929999293002930129302293032930429999293052930629307293082930929999293102931129312293132931429999293152931629317293182931929999293202932129322293232932429999293252932629327293282932929999293302933129332293332933429999293352933629337293382933929999293402934129342293432934429999293452934629347293482934929999293502935129352293532935429999293552935629357293582935929999293602936129362293632936429999293652936629367293682936929999293702937129372293732937429999293752937629377293782937929999293802938129382293832938429999293852938629387293882938929999293902939129392293932939429999293952939629397293982939929999294002940129402294032940429999294052940629407294082940929999294102941129412294132941429999294152941629417294182941929999294202942129422294232942429999294252942629427294282942929999294302943129432294332943429999294352943629437294382943929999294402944129442294432944429999294452944629447294482944929999294502945129452294532945429999294552945629457294582945929999294602946129462294632946429999294652946629467294682946929999294702947129472294732947429999294752947629477294782947929999294802948129482294832948429999294852948629487294882948929999294902949129492294932949429999294952949629497294982949929999295002950129502295032950429999295052950629507295082950929999295102951129512295132951429999295152951629517295182951929999295202952129522295232952429999295252952629527295282952929999295302953129532295332953429999295352953629537295382953929999295402954129542295432954429999295452954629547295482954929999295502955129552295532955429999295552955629557295582955929999295602956129562295632956429999295652956629567295682956929999295702957129572295732957429999295752957629577295782957929999295802958129582295832958429999295852958629587295882958929999295902959129592295932959429999295952959629597295982959929999296002960129602296032960429999296052960629607296082960929999296102961129612296132961429999296152961629617296182961929999296202962129622296232962429999296252962629627296282962929999296302963129632296332963429999296352963629637296382963929999296402964129642296432964429999296452964629647296482964929999296502965129652296532965429999296552965629657296582965929999296602966129662296632966429999296652966629667296682966929999296702967129672296732967429999296752967629677296782967929999296802968129682296832968429999296852968629687296882968929999296902969129692296932969429999296952969629697296982969929999297002970129702297032970429999297052970629707297082970929999297102971129712297132971429999297152971629717297182971929999297202972129722297232972429999297252972629727297282972929999297302973129732297332973429999297352973629737297382973929999297402974129742297432974429999297452974629747297482974929999297502975129752297532975429999297552975629757297582975929999297602976129762297632976429999297652976629767297682976929999297702977129772297732977429999297752977629777297782977929999297802978129782297832978429999297852978629787297882978929999297902979129792297932979429999297952979629797297982979929999298002980129802298032980429999298052980629807298082980929999298102981129812298132981429999298152981629817298182981929999298202982129822298232982429999298252982629827298282982929999298302983129832298332983429999298352983629837298382983929999298402984129842298432984429999298452984629847298482984929999298502985129852298532985429999298552985629857298582985929999298602986129862298632986429999298652986629867298682986929999298702987129872298732987429999298752987629877298782987929999298802988129882298832988429999298852988629887298882988929999298902989129892298932989429999298952989629897298982989929999299002990129902299032990429999299052990629907299082990929999299102991129912299132991429999299152991629917299182991929999299202992129922299232992429999299252992629927299282992929999299302993129932299332993429999299352993629937299382993929999299402994129942299432994429999299452994629947299482994929999299502995129952299532995429999299552995629957299582995929999299602996129962299632996429999299652996629967299682996929999299702997129972299732997429999299752997629977299782997929999299802998129982299832998429999299852998629987299882998929999299902999129992299932999429999299952999629997299982999929999
\ No newline at end of file
diff --git a/airlift-zstd/src/test/resources/data/zstd/multiple-frames b/airlift-zstd/src/test/resources/data/zstd/multiple-frames
new file mode 100644
index 00000000000..5e018aa9551
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/multiple-frames
@@ -0,0 +1,406 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+
diff --git a/airlift-zstd/src/test/resources/data/zstd/multiple-frames.zst b/airlift-zstd/src/test/resources/data/zstd/multiple-frames.zst
new file mode 100644
index 00000000000..4a9e6582a36
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/multiple-frames.zst
diff --git a/airlift-zstd/src/test/resources/data/zstd/offset-before-start.zst b/airlift-zstd/src/test/resources/data/zstd/offset-before-start.zst
new file mode 100644
index 00000000000..0928f5f35f1
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/offset-before-start.zst
diff --git a/airlift-zstd/src/test/resources/data/zstd/small-literals-after-incompressible-literals b/airlift-zstd/src/test/resources/data/zstd/small-literals-after-incompressible-literals
new file mode 100644
index 00000000000..51eef21f9d3
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/small-literals-after-incompressible-literals
diff --git a/airlift-zstd/src/test/resources/data/zstd/with-checksum b/airlift-zstd/src/test/resources/data/zstd/with-checksum
new file mode 100644
index 00000000000..6b0b1270ff0
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/with-checksum
@@ -0,0 +1,203 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+
diff --git a/airlift-zstd/src/test/resources/data/zstd/with-checksum.zst b/airlift-zstd/src/test/resources/data/zstd/with-checksum.zst
new file mode 100644
index 00000000000..885ffb8855e
--- /dev/null
+++ b/airlift-zstd/src/test/resources/data/zstd/with-checksum.zst