#export LD_LIBRARY_PATH=/home/dong/2019-nCoV/_install/lib:$LD_LIBRARY_PATH
#export PKG_CONFIG_PATH=/home/dong/2019-nCoV/_install/lib/pkgconfig:$PKG_CONFIG_PATH

#export LD_LIBRARY_PATH=/home/dong/2019-nCoV/_install/usr/local/lib:$LD_LIBRARY_PATH
#export PKG_CONFIG_PATH=/home/dong/2019-nCoV/_install/usr/local/lib/pkgconfig:$PKG_CONFIG_PATH

#echo "export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/dong/2019-nCoV/_install/lib">> ~/.bashrc
#echo "export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:/home/dong/2019-nCoV/_install/lib/pkgconfig">> ~/.bashrc

#echo "export LD_LIBRARY_PATH=/home/dong/2019-nCoV/_install/lib:$LD_LIBRARY_PATH">> ~/.bashrc
#echo "export PKG_CONFIG_PATH=/home/dong/2019-nCoV/_install/lib/pkgconfig:$PKG_CONFIG_PATH">> ~/.bashrc

#source ~/.bashrc

#1
tar xvf yasm-1.2.0.tar.gz
cd yasm-1.2.0
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#2
tar xvf nasm-2.13.03.tar.gz
cd nasm-2.13.03
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#3
tar xvf zlib-1.2.11.tar.gz
cd zlib-1.2.11
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared #--enable-static
make && make install
cd ..

#4
tar xvf last_x264.tar.bz2
cd x264-snapshot-20190512-2245
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#5
tar xvf x265_2.9.tar.gz
cd x265_2.9/build/linux
./make-Makefiles.bash
make
make DESTDIR=/home/dong/2019-nCoV/_install install
cd ../../..

#echo "export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/dong/2019-nCoV/_install/usr/local/lib">> ~/.bashrc
#echo "export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:/home/dong/2019-nCoV/_install/usr/local/lib/pkgconfig">> ~/.bashrc
#source ~/.bashrc

#cp -R /home/dong/2019-nCoV/_install/usr/local/* /home/dong/2019-nCoV/_install
#vi x265.pc
#prefix=/usr/local ---> prefix=/home/dong/2019-nCoV/_install

#6
tar xvf libvpx-1.8.0.tar.gz
cd libvpx-1.8.0
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#7
tar xvf fdk-aac-2.0.0.tar.gz
cd fdk-aac-2.0.0
./configure prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#8
tar xvf xvidcore_1.3.3.orig.tar.gz
cd xvidcore-1.3.3/build/generic
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ../../..

#9
tar xvf libogg-1.3.4.tar.gz
cd libogg-1.3.4
./configure prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#10
tar xvf libvorbis-1.3.6.tar.gz
cd libvorbis-1.3.6
./configure prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#11
tar xvf lame-3.100.tar.gz
cd lame-3.100
./configure prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#12
tar xvf opencore-amr-0.1.3.tar.gz
cd opencore-amr-0.1.3
./configure prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#13
tar xvf SDL-1.2.15.tar.gz
cd SDL-1.2.15
sed -e ''/_XData32/s:register long:register _Xconst long:'' -i src/video/x11/SDL_x11sym.h
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --disable-static
make && make install
cd ..

#14
tar xvf SDL2-2.0.10.tar.gz
cd SDL2-2.0.10
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static
make && make install
cd ..

#15
tar xvf ffmpeg-4.1.tar.bz2
cd ffmpeg-4.1
./configure --prefix=/home/dong/2019-nCoV/_install --enable-shared --enable-static --enable-ffplay --enable-libx264 --enable-libx265 --enable-gpl --enable-libxvid --enable-libvpx --enable-libvorbis --enable-libmp3lame --enable-libopencore-amrnb --enable-libopencore-amrwb --enable-version3 --enable-libfdk-aac --enable-nonfree --enable-postproc --disable-vaapi --extra-cflags=-I/home/dong/2019-nCoV/_install/include --extra-cxxflags=-I/home/dong/2019-nCoV/_install/include --extra-ldflags=-L/home/dong/2019-nCoV/_install/lib #
make && make install
cd ..

/*
 * Copyright (c) 2014 Stefano Sabatini
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * @file
 * libavformat AVIOContext API example.
 *
 * Make libavformat demuxer access media content through a custom
 * AVIOContext read callback.
 * @example avio_reading.c
 */

#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>
#include <libavformat/avio.h>
#include <libavutil/file.h>

struct buffer_data {
    uint8_t *ptr;
    size_t size; ///< size left in the buffer
};

static int read_packet(void *opaque, uint8_t *buf, int buf_size)
{
    struct buffer_data *bd = (struct buffer_data *)opaque;
    buf_size = FFMIN(buf_size, bd->size);

    if (!buf_size)
        return AVERROR_EOF;
    printf("ptr:%p size:%zu\n", bd->ptr, bd->size);

    /* copy internal buffer data to buf */
    memcpy(buf, bd->ptr, buf_size);
    bd->ptr  += buf_size;
    bd->size -= buf_size;

    return buf_size;
}

int main(int argc, char *argv[])
{
    AVFormatContext *fmt_ctx = NULL;
    AVIOContext *avio_ctx = NULL;
    uint8_t *buffer = NULL, *avio_ctx_buffer = NULL;
    size_t buffer_size, avio_ctx_buffer_size = 4096;
    char *input_filename = NULL;
    int ret = 0;
    struct buffer_data bd = { 0 };

    if (argc != 2) {
        fprintf(stderr, "usage: %s input_file\n"
                "API example program to show how to read from a custom buffer "
                "accessed through AVIOContext.\n", argv[0]);
        return 1;
    }
    input_filename = argv[1];

    /* slurp file content into buffer */
    ret = av_file_map(input_filename, &buffer, &buffer_size, 0, NULL);
    if (ret < 0)
        goto end;

    /* fill opaque structure used by the AVIOContext read callback */
    bd.ptr  = buffer;
    bd.size = buffer_size;

    if (!(fmt_ctx = avformat_alloc_context())) {
        ret = AVERROR(ENOMEM);
        goto end;
    }

    avio_ctx_buffer = av_malloc(avio_ctx_buffer_size);
    if (!avio_ctx_buffer) {
        ret = AVERROR(ENOMEM);
        goto end;
    }
    avio_ctx = avio_alloc_context(avio_ctx_buffer, avio_ctx_buffer_size,
                                  0, &bd, &read_packet, NULL, NULL);
    if (!avio_ctx) {
        ret = AVERROR(ENOMEM);
        goto end;
    }
    fmt_ctx->pb = avio_ctx;

    ret = avformat_open_input(&fmt_ctx, NULL, NULL, NULL);
    if (ret < 0) {
        fprintf(stderr, "Could not open input\n");
        goto end;
    }

    ret = avformat_find_stream_info(fmt_ctx, NULL);
    if (ret < 0) {
        fprintf(stderr, "Could not find stream information\n");
        goto end;
    }

    av_dump_format(fmt_ctx, 0, input_filename, 0);

end:
    avformat_close_input(&fmt_ctx);
    /* note: the internal buffer could have changed, and be != avio_ctx_buffer */
    if (avio_ctx) {
        av_freep(&avio_ctx->buffer);
        av_freep(&avio_ctx);
    }
    av_file_unmap(buffer, buffer_size);

    if (ret < 0) {
        fprintf(stderr, "Error occurred: %s\n", av_err2str(ret));
        return 1;
    }

    return 0;
}

export LD_LIBRARY_PATH=$(pwd)/_install/lib:$LD_LIBRARY_PATH

#gcc -o transcoding transcoding.c \
gcc -o muxing muxing.c \
-I $(pwd) \
-I $(pwd)/_install/include \
-I $(pwd)/_install/include/libavcodec \
-I $(pwd)/_install/include/libavdevice \
-I $(pwd)/_install/include/libavfilter \
-I $(pwd)/_install/include/libavformat \
-I $(pwd)/_install/include/libavutil \
-I $(pwd)/_install/include/libpostproc \
-I $(pwd)/_install/include/libswresample \
-I $(pwd)/_install/include/libswscale \
-I $(pwd)/_install/include/libpostproc \
-I $(pwd)/_install/include/libyasm \
-I $(pwd)/_install/include/SDL \
-I $(pwd)/_install/include/SDL2 \
-L $(pwd)/_install/lib \
-Wno-deprecated-declarations -lx264 -lx265 -lSDL -lSDL2 -lavformat -lavutil -lavdevice -lavcodec -lswresample -lavfilter -lswscale -lpostproc -lz -lm -lpthread

/*
 * Copyright (c) 2014 Stefano Sabatini
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * @file
 * libavformat AVIOContext API example.
 *
 * Make libavformat demuxer access media content through a custom
 * AVIOContext read callback.
 * @example avio_reading.c
 */

#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>
#include <libavformat/avio.h>
#include <libavutil/file.h>

#define Custom_AVIOContext (0)

#if Custom_AVIOContext
struct buffer_data {
    uint8_t *ptr;
    size_t size; ///< size left in the buffer
};

static int read_packet(void *opaque, uint8_t *buf, int buf_size)
{
    struct buffer_data *bd = (struct buffer_data *)opaque;
    buf_size = FFMIN(buf_size, bd->size);

    if (!buf_size)
        return AVERROR_EOF;
    printf("ptr:%p size:%zu\n", bd->ptr, bd->size);

    /* copy internal buffer data to buf */
    memcpy(buf, bd->ptr, buf_size);
    bd->ptr  += buf_size;
    bd->size -= buf_size;

    return buf_size;
}
#endif

int main(int argc, char *argv[])
{
    AVFormatContext *fmt_ctx = NULL;
    char *input_filename = argv[1];
    int ret = 0;

    if (argc != 2) {
        fprintf(stderr, "usage: %s input_file\n"
                "API example program to show how to read from a custom buffer "
                "accessed through AVIOContext.\n", argv[0]);
        return 1;
    }

#if Custom_AVIOContext
    AVIOContext *avio_ctx = NULL;
    uint8_t *buffer = NULL, *avio_ctx_buffer = NULL;
    size_t buffer_size, avio_ctx_buffer_size = 4096;      
    struct buffer_data bd = { 0 };

    /* slurp file content into buffer */
    ret = av_file_map(input_filename, &buffer, &buffer_size, 0, NULL);
    if (ret < 0)
        goto end;

    /* fill opaque structure used by the AVIOContext read callback */
    bd.ptr  = buffer;
    bd.size = buffer_size;

    if (!(fmt_ctx = avformat_alloc_context())) {
        ret = AVERROR(ENOMEM);
        goto end;
    }

    avio_ctx_buffer = av_malloc(avio_ctx_buffer_size);
    if (!avio_ctx_buffer) {
        ret = AVERROR(ENOMEM);
        goto end;
    }
    avio_ctx = avio_alloc_context(avio_ctx_buffer, avio_ctx_buffer_size,
                                  0, &bd, &read_packet, NULL, NULL);
    if (!avio_ctx) {
        ret = AVERROR(ENOMEM);
        goto end;
    }
    fmt_ctx->pb = avio_ctx;


    ret = avformat_open_input(&fmt_ctx, NULL, NULL, NULL);
#else
    ret = avformat_open_input(&fmt_ctx, input_filename, NULL, NULL);
#endif
    if (ret < 0) {
        fprintf(stderr, "Could not open input\n");
        goto end;
    }

    ret = avformat_find_stream_info(fmt_ctx, NULL);
    if (ret < 0) {
        fprintf(stderr, "Could not find stream information\n");
        goto end;
    }

    av_dump_format(fmt_ctx, 0, input_filename, 0);

end:
    avformat_close_input(&fmt_ctx);

#if Custom_AVIOContext
    /* note: the internal buffer could have changed, and be != avio_ctx_buffer */
    if (avio_ctx) {
        av_freep(&avio_ctx->buffer);
        av_freep(&avio_ctx);
    }
    av_file_unmap(buffer, buffer_size);
#endif

    if (ret < 0) {
        fprintf(stderr, "Error occurred: %s\n", av_err2str(ret));
        return 1;
    }

    return 0;
}

if (argc <= 2) {
        fprintf(stderr, "Usage: %s <input file> <output file>\n", argv[0]);
        exit(0);
    }
    filename    = argv[1];
    outfilename = argv[2];

    pkt = av_packet_alloc();
    if (!pkt)
        exit(1);

    /* set end of buffer to 0 (this ensures that no overreading happens for damaged MPEG streams) */
    memset(inbuf + INBUF_SIZE, 0, AV_INPUT_BUFFER_PADDING_SIZE);

    /* find the MPEG-1 video decoder */
    //codec = avcodec_find_decoder(AV_CODEC_ID_MPEG1VIDEO);
    codec = avcodec_find_decoder(AV_CODEC_ID_H264);
    if (!codec) {
        fprintf(stderr, "Codec not found\n");
        exit(1);
    }

ret = avcodec_send_packet(dec_ctx, pkt);
while (ret >= 0) {
    ret = avcodec_receive_frame(dec_ctx, frame); }

/*
 * Copyright (c) 2015 Ludmila Glinskih
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/**
 * H264 codec test.
 */

#define Custom_AVIOContext (1)

#include "libavutil/adler32.h"
#include "libavcodec/avcodec.h"
#include "libavformat/avformat.h"
#include "libavutil/imgutils.h"

#if Custom_AVIOContext
#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>
#include <libavformat/avio.h>
#include <libavutil/file.h>

struct buffer_data {
    uint8_t *ptr;
    size_t size; ///< size left in the buffer
};

static int read_packet(void *opaque, uint8_t *buf, int buf_size)
{
    struct buffer_data *bd = (struct buffer_data *)opaque;
    buf_size = FFMIN(buf_size, bd->size);

    if (!buf_size)
        return AVERROR_EOF;

    //printf("ptr:%p size:%zu\n", bd->ptr, bd->size);
    //printf("buf_size:%d\n", buf_size);

    /* copy internal buffer data to buf */
    memcpy(buf, bd->ptr, buf_size);
    bd->ptr  += buf_size;
    bd->size -= buf_size;

    return buf_size;
}
#endif

static int video_decode_example(const char *input_filename)
{
    AVCodec *codec = NULL;
    AVCodecContext *ctx= NULL;
    AVCodecParameters *origin_par = NULL;
    AVFrame *fr = NULL;
    uint8_t *byte_buffer = NULL;
    AVPacket pkt;
    AVFormatContext *fmt_ctx = NULL;
    int number_of_written_bytes;
    int video_stream;
    int got_frame = 0;
    int byte_buffer_size;
    int i = 0;
    int result;
    int end_of_stream = 0;\

#if Custom_AVIOContext
    AVIOContext *avio_ctx = NULL;
    uint8_t *buffer = NULL, *avio_ctx_buffer = NULL;
    size_t buffer_size, avio_ctx_buffer_size = 4096;
    int ret = 0;
    struct buffer_data bd = { 0 };

    /* slurp file content into buffer */
    ret = av_file_map(input_filename, &buffer, &buffer_size, 0, NULL);
    if (ret < 0)
        return -1;

    /* fill opaque structure used by the AVIOContext read callback */
    bd.ptr  = buffer;
    bd.size = buffer_size;

    if (!(fmt_ctx = avformat_alloc_context())) {
        ret = AVERROR(ENOMEM);
        return -1;
    }

    avio_ctx_buffer = av_malloc(avio_ctx_buffer_size);
    if (!avio_ctx_buffer) {
        ret = AVERROR(ENOMEM);
        return -1;
    }
    avio_ctx = avio_alloc_context(avio_ctx_buffer, avio_ctx_buffer_size,
                                  0, &bd, &read_packet, NULL, NULL);
    if (!avio_ctx) {
        ret = AVERROR(ENOMEM);
        return -1;
    }
    fmt_ctx->pb = avio_ctx;

    
    result = avformat_open_input(&fmt_ctx, NULL, NULL, NULL);
#else
    result = avformat_open_input(&fmt_ctx, input_filename, NULL, NULL);
#endif

    if (result < 0) {
        av_log(NULL, AV_LOG_ERROR, "Can''t open file\n");
        return result;
    }

    result = avformat_find_stream_info(fmt_ctx, NULL);
    if (result < 0) {
        av_log(NULL, AV_LOG_ERROR, "Can''t get stream info\n");
        return result;
    }

    video_stream = av_find_best_stream(fmt_ctx, AVMEDIA_TYPE_VIDEO, -1, -1, NULL, 0);
    if (video_stream < 0) {
      av_log(NULL, AV_LOG_ERROR, "Can''t find video stream in input file\n");
      return -1;
    }

    origin_par = fmt_ctx->streams[video_stream]->codecpar;

    codec = avcodec_find_decoder(origin_par->codec_id);
    if (!codec) {
        av_log(NULL, AV_LOG_ERROR, "Can''t find decoder\n");
        return -1;
    }

    ctx = avcodec_alloc_context3(codec);
    if (!ctx) {
        av_log(NULL, AV_LOG_ERROR, "Can''t allocate decoder context\n");
        return AVERROR(ENOMEM);
    }

    result = avcodec_parameters_to_context(ctx, origin_par);
    if (result) {
        av_log(NULL, AV_LOG_ERROR, "Can''t copy decoder context\n");
        return result;
    }

    result = avcodec_open2(ctx, codec, NULL);
    if (result < 0) {
        av_log(ctx, AV_LOG_ERROR, "Can''t open decoder\n");
        return result;
    }

    fr = av_frame_alloc();
    if (!fr) {
        av_log(NULL, AV_LOG_ERROR, "Can''t allocate frame\n");
        return AVERROR(ENOMEM);
    }

    byte_buffer_size = av_image_get_buffer_size(ctx->pix_fmt, ctx->width, ctx->height, 16);
    byte_buffer = av_malloc(byte_buffer_size);
    if (!byte_buffer) {
        av_log(NULL, AV_LOG_ERROR, "Can''t allocate buffer\n");
        return AVERROR(ENOMEM);
    }

    printf("#tb %d: %d/%d\n", video_stream, fmt_ctx->streams[video_stream]->time_base.num, fmt_ctx->streams[video_stream]->time_base.den);
    i = 0;
    av_init_packet(&pkt);
    do {
        if (!end_of_stream)
            if (av_read_frame(fmt_ctx, &pkt) < 0)
                end_of_stream = 1;
        if (end_of_stream) {
            pkt.data = NULL;
            pkt.size = 0;
        }
        if (pkt.stream_index == video_stream || end_of_stream) {
            got_frame = 0;
            if (pkt.pts == AV_NOPTS_VALUE)
                pkt.pts = pkt.dts = i;
            result = avcodec_decode_video2(ctx, fr, &got_frame, &pkt);
            if (result < 0) {
                av_log(NULL, AV_LOG_ERROR, "Error decoding frame\n");
                return result;
            }
            if (got_frame) {
                number_of_written_bytes = av_image_copy_to_buffer(byte_buffer, byte_buffer_size,
                                        (const uint8_t* const *)fr->data, (const int*) fr->linesize,
                                        ctx->pix_fmt, ctx->width, ctx->height, 1);
                if (number_of_written_bytes < 0) {
                    av_log(NULL, AV_LOG_ERROR, "Can''t copy image to buffer\n");
                    return number_of_written_bytes;
                }

                //printf("number_of_written_bytes %d %dx%d\n", number_of_written_bytes, ctx->width, ctx->height);

                printf("%d, %10"PRId64", %10"PRId64", %8"PRId64", %8d, 0x%08lx\n", video_stream,
                        fr->pts, fr->pkt_dts, fr->pkt_duration,
                        number_of_written_bytes, av_adler32_update(0, (const uint8_t*)byte_buffer, number_of_written_bytes));
            }
            av_packet_unref(&pkt);
            av_init_packet(&pkt);
        }
        i++;
    } while (!end_of_stream || got_frame);

    av_packet_unref(&pkt);
    av_frame_free(&fr);
    avcodec_close(ctx);
    avformat_close_input(&fmt_ctx);
    avcodec_free_context(&ctx);
    av_freep(&byte_buffer);
    return 0;
}

int main(int argc, char **argv)
{
    if (argc < 2)
    {
        av_log(NULL, AV_LOG_ERROR, "Incorrect input\n");
        return 1;
    }

    if (video_decode_example(argv[1]) != 0)
        return 1;

    return 0;
}

// tutorial01.c
// Code based on a tutorial by Martin Bohme (boehme@inb.uni-luebeckREMOVETHIS.de)
// Tested on Gentoo, CVS version 5/01/07 compiled with GCC 4.1.1
// With updates from https://github.com/chelyaev/ffmpeg-tutorial
// Updates tested on:
// LAVC 54.59.100, LAVF 54.29.104, LSWS 2.1.101 
// on GCC 4.7.2 in Debian February 2015

// A small sample program that shows how to use libavformat and libavcodec to
// read video from a file.
//
// Use
//
// gcc -o tutorial01 tutorial01.c -lavformat -lavcodec -lswscale -lz
//
// to build (assuming libavformat and libavcodec are correctly installed
// your system).
//
// Run using
//
// tutorial01 myvideofile.mpg
//
// to write the first five frames from "myvideofile.mpg" to disk in PPM
// format.

#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>
#include <libswscale/swscale.h>

#include <stdio.h>

// compatibility with newer API
#if LIBAVCODEC_VERSION_INT < AV_VERSION_INT(55,28,1)
#define av_frame_alloc avcodec_alloc_frame
#define av_frame_free avcodec_free_frame
#endif

void SaveFrame(AVFrame *pFrame, int width, int height, int iFrame) {
  FILE *pFile;
  char szFilename[32];
  int  y;
  
  // Open file
  sprintf(szFilename, "frame%d.ppm", iFrame);
  pFile=fopen(szFilename, "wb");
  if(pFile==NULL)
    return;
  
  // Write header
  fprintf(pFile, "P6\n%d %d\n255\n", width, height);
  
  // Write pixel data
  for(y=0; y<height; y++)
    fwrite(pFrame->data[0]+y*pFrame->linesize[0], 1, width*3, pFile);
  
  // Close file
  fclose(pFile);
}

#define Custom_AVIOContext (1)

#if Custom_AVIOContext
#include <libavcodec/avcodec.h>
#include <libavformat/avformat.h>
#include <libavformat/avio.h>
#include <libavutil/file.h>

struct buffer_data {
    uint8_t *ptr;
    size_t size; ///< size left in the buffer
};

static int read_packet(void *opaque, uint8_t *buf, int buf_size)
{
    struct buffer_data *bd = (struct buffer_data *)opaque;
    buf_size = FFMIN(buf_size, bd->size);

    if (!buf_size)
        return AVERROR_EOF;

    //printf("ptr:%p size:%zu\n", bd->ptr, bd->size);
    //printf("buf_size:%d\n", buf_size);

    /* copy internal buffer data to buf */
    memcpy(buf, bd->ptr, buf_size);
    bd->ptr  += buf_size;
    bd->size -= buf_size;

    return buf_size;
}
#endif

int main(int argc, char *argv[]) {
  // Initalizing these to NULL prevents segfaults!
  AVFormatContext   *pFormatCtx = NULL;
  int               i, videoStream;
  AVCodecContext    *pCodecCtxOrig = NULL;
  AVCodecContext    *pCodecCtx = NULL;
  AVCodec           *pCodec = NULL;
  AVFrame           *pFrame = NULL;
  AVFrame           *pFrameRGB = NULL;
  AVPacket          packet;
  int               frameFinished;
  int               numBytes;
  uint8_t           *buffer = NULL;
  struct SwsContext *sws_ctx = NULL;

  if(argc < 2) {
    printf("Please provide a movie file\n");
    return -1;
  }
  // Register all formats and codecs
  av_register_all();

#if Custom_AVIOContext
    AVIOContext *avio_ctx = NULL;
    uint8_t *avio_ctx_buffer = NULL;
    size_t buffer_size, avio_ctx_buffer_size = 4096;
    int ret = 0;
    struct buffer_data bd = { 0 };

    /* slurp file content into buffer */
    ret = av_file_map(argv[1], &buffer, &buffer_size, 0, NULL);
    if (ret < 0)
        return -1;

    /* fill opaque structure used by the AVIOContext read callback */
    bd.ptr  = buffer;
    bd.size = buffer_size;

    if (!(pFormatCtx = avformat_alloc_context())) {
        ret = AVERROR(ENOMEM);
        return -1;
    }

    avio_ctx_buffer = av_malloc(avio_ctx_buffer_size);
    if (!avio_ctx_buffer) {
        ret = AVERROR(ENOMEM);
        return -1;
    }
    avio_ctx = avio_alloc_context(avio_ctx_buffer, avio_ctx_buffer_size,
                                  0, &bd, &read_packet, NULL, NULL);
    if (!avio_ctx) {
        ret = AVERROR(ENOMEM);
        return -1;
    }
    pFormatCtx->pb = avio_ctx;

    
  // Open video file
  if(avformat_open_input(&pFormatCtx, NULL, NULL, NULL)!=0)
    return -1; // Couldn''t open file
#else
  // Open video file
  if(avformat_open_input(&pFormatCtx, argv[1], NULL, NULL)!=0)
    return -1; // Couldn''t open file
#endif
  

  
  // Retrieve stream information
  if(avformat_find_stream_info(pFormatCtx, NULL)<0)
    return -1; // Couldn''t find stream information
  
  // Dump information about file onto standard error
  av_dump_format(pFormatCtx, 0, argv[1], 0);
  
  // Find the first video stream
  videoStream=-1;
  for(i=0; i<pFormatCtx->nb_streams; i++)
    if(pFormatCtx->streams[i]->codec->codec_type==AVMEDIA_TYPE_VIDEO) {
      videoStream=i;
      break;
    }
  if(videoStream==-1)
    return -1; // Didn''t find a video stream
  
  // Get a pointer to the codec context for the video stream
  pCodecCtxOrig=pFormatCtx->streams[videoStream]->codec;
  // Find the decoder for the video stream
  pCodec=avcodec_find_decoder(pCodecCtxOrig->codec_id);
  if(pCodec==NULL) {
    fprintf(stderr, "Unsupported codec!\n");
    return -1; // Codec not found
  }
  // Copy context
  pCodecCtx = avcodec_alloc_context3(pCodec);
  if(avcodec_copy_context(pCodecCtx, pCodecCtxOrig) != 0) {
    fprintf(stderr, "Couldn''t copy codec context");
    return -1; // Error copying codec context
  }

  // Open codec
  if(avcodec_open2(pCodecCtx, pCodec, NULL)<0)
    return -1; // Could not open codec
  
  // Allocate video frame
  pFrame=av_frame_alloc();
  
  // Allocate an AVFrame structure
  pFrameRGB=av_frame_alloc();
  if(pFrameRGB==NULL)
    return -1;

  // Determine required buffer size and allocate buffer
  numBytes=avpicture_get_size(AV_PIX_FMT_RGB24, pCodecCtx->width,
                  pCodecCtx->height);
  buffer=(uint8_t *)av_malloc(numBytes*sizeof(uint8_t));
  
  // Assign appropriate parts of buffer to image planes in pFrameRGB
  // Note that pFrameRGB is an AVFrame, but AVFrame is a superset
  // of AVPicture
  avpicture_fill((AVPicture *)pFrameRGB, buffer, AV_PIX_FMT_RGB24,
         pCodecCtx->width, pCodecCtx->height);
  
  // initialize SWS context for software scaling
  sws_ctx = sws_getContext(pCodecCtx->width,
               pCodecCtx->height,
               pCodecCtx->pix_fmt,
               pCodecCtx->width,
               pCodecCtx->height,
               AV_PIX_FMT_RGB24,
               SWS_BILINEAR,
               NULL,
               NULL,
               NULL
               );

  // Read frames and save first five frames to disk
  i=0;
  while(av_read_frame(pFormatCtx, &packet)>=0) {
    // Is this a packet from the video stream?
    if(packet.stream_index==videoStream) {
      // Decode video frame
      avcodec_decode_video2(pCodecCtx, pFrame, &frameFinished, &packet);
      
      // Did we get a video frame?
      if(frameFinished) {
    // Convert the image from its native format to RGB
    sws_scale(sws_ctx, (uint8_t const * const *)pFrame->data,
          pFrame->linesize, 0, pCodecCtx->height,
          pFrameRGB->data, pFrameRGB->linesize);
    
    // Save the frame to disk
    if(++i<=5)
      SaveFrame(pFrameRGB, pCodecCtx->width, pCodecCtx->height, 
            i);
      }
    }
    
    // Free the packet that was allocated by av_read_frame
    av_free_packet(&packet);
  }
  
  // Free the RGB image
  av_free(buffer);
  av_frame_free(&pFrameRGB);
  
  // Free the YUV frame
  av_frame_free(&pFrame);
  
  // Close the codecs
  avcodec_close(pCodecCtx);
  avcodec_close(pCodecCtxOrig);

  // Close the video file
  avformat_close_input(&pFormatCtx);
  
  return 0;
}

fmt = oc->oformat;

    fmt->video_codec = AV_CODEC_ID_H264; 
    fmt->audio_codec = AV_CODEC_ID_MP2;   //ffmpeg-4.2.2 default support
    //fmt->audio_codec = AV_CODEC_ID_AAC; //ffmpeg-4.1 default support

    /* Add the audio and video streams using the default format codecs
     * and initialize the codecs. */
    if (fmt->video_codec != AV_CODEC_ID_NONE) {
        add_stream(&video_st, oc, &video_codec, fmt->video_codec);
        have_video = 1;
        encode_video = 1;
    }
    if (fmt->audio_codec != AV_CODEC_ID_NONE) {
        add_stream(&audio_st, oc, &audio_codec, fmt->audio_codec);
        have_audio = 1;
        encode_audio = 1;
    }

#include <stdio.h>
using namespace std;
int num[3],f,f1;
int move(int n,int a,int b)
{
    //printf("Move disk %d from %c to %c\n",n,a,b);
    num[a]--,num[b]++;
    if(num[0]==num[1]&&num[1]==num[2])return 1;
    return 0;
}
void hanoi(int n,int a,int b,int c)
{
    if(f1)return;
    if(n==1)
    {
        if(move(n,a,c))
        {
            printf("%d\n",f);
            f1=1;
            return;
        }
    }
    else
    {
        hanoi(n-1,a,c,b);
        f++;
        if(move(n,a,c))
        {
            printf("%d\n",f);
            f1=1;
            return;
        }
        hanoi(n-1,b,a,c);
    }
}
int main()
{
    int n;
    for(int n=3; n<=30; n+=3)
    {
        num[0]=n,num[1]=num[2]=f=0,f1=0;
        hanoi(n,0,1,2);
    }
    return 0;
}

import java.math.*;
import java.util.*;
public class Main
{
    public static void main(String args[])
    {
        Scanner cin=new Scanner(System.in);
        BigInteger tmp=BigInteger.ZERO;
        for(int n=3; n<=300; n+=3)
        {
            if(n/3%2==1)
            {
                System.out.println("\""+tmp.multiply(BigInteger.valueOf(4))
                .add(BigInteger.valueOf(2))+"\",");
            }
            else
            {
                int x=n-n/3-1;
                int y=n/3-1;
                tmp=cal(x).add(cal(y)).subtract(BigInteger.ONE);
                System.out.println("\""+tmp+"\",");
            }
        }
    }
    static BigInteger cal(int x)
    {
        BigInteger ans=BigInteger.ONE;
        ans=ans.shiftLeft(x);
        return ans;
    }
}

/*
    题意：求出出现次数最多的数字
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,n,a[100010];
char s[110];
int main(){
    scanf("%d",&T);
    while(T--){
    	memset(a, 0, sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        	int p;
            scanf(" %s %d",&s,&p);
            a[p]++;
        }
        int mx=0,ans;
        for(int i=11111;i<=99999;i++)mx=max(mx,a[i]);
        for(int i=11111;i<=99999;i++)if(mx==a[i]){ans=i;break;}
        printf("%d\n", ans);
    }return 0;
}　

/*
    题目大意：b串可允许多次的任意两个字符交换，问最终a串和b串的最长公共前缀
    题解：记录b串中每个元素的个数，将a串从头到尾扫描匹配，直到b无字符能与a当前位置匹配
*/
#include <cstdio>
#include <algorithm>
#include <cstring> 
using namespace std;
int T,a[26],b[26];
char s[100010],t[100010];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",&s);
        scanf("%s",&t);
        memset(b,0,sizeof(b));
        int n=strlen(t);
        for(int i=0;i<n;i++)b[t[i]-''a'']++;
        n=strlen(s);
		int ans=0;
		for(int i=0;i<n;i++){
			if(b[s[i]-''a'']){
				ans++;
				b[s[i]-''a'']--;
			}else break;
		}
		printf("%d\n",ans);
    }
    return 0;
}

/*
    输出最大的数字所在的位置
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int T,a,b,c;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&a,&b,&c);
        if(c<a&&c<b)puts("Third");
        else if(b<a&&b<c)puts("Second");
        else puts("First");
    }return 0;
}

/*
    组合数取模
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL P=1000000007;
namespace Comb{
    const int U=200000;
    int f[U+3],rf[U+3];
    LL inv(LL a,LL m){return(a==1?1:inv(m%a,m)*(m-m/a)%m);} 
    void init(){
        f[0]=1;for(int i=1;i<=U;i++)f[i]=(LL)f[i-1]*i%P;
        rf[U]=inv(f[U],P);
        for(int i=U;i;i--)rf[i-1]=(LL)rf[i]*i%P;
    }
    LL C(int n,int m){
        if(m<0||m>n)return 0;
        return (LL)f[n]*rf[m]%P*rf[n-m]%P;
    }
}
int main(){
    int T,a,b;
    Comb::init();
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&a,&b);
        printf("%lld\n",Comb::C(a-1,b)*2%P);
    }return 0;
}

/*
    输出a+b-1
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    int T,a,b;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&a,&b);
        printf("%d\n",a+b-1);
    }return 0;
}

/*
    题目大意：每次需要使用材料的时候都要从冰箱中取出，但是冰箱外最多放置k种不同的材料
    所以当取出第k+1种时，必须要放回去一种，当需要使用的材料在外面时就不需要打开冰箱，
    问打开冰箱的最小次数
    题解：我们统计每个数字下一次出现的位置，作为优先队列的关键字，
    我们将放置在外面的材料放入优先队列，每次需要把材料放回冰箱里的时候，
    我们选取下次出现时间最晚的材料即可
*/
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef pair<int,int> P;
priority_queue<P,vector<P> >Q;
const int N=500010;
int T,n,k,a[N],nxt[N],lst[N];
bool inq[N];
int main(){
    scanf("%d",&T);
    while(T--){
        int cnt=0,ans=0;
        scanf("%d%d",&n,&k);
        map<int,int> M;
        for(int i=1;i<=n;i++)lst[i]=n+1;
        for(int i=1;i<=n;i++){
        	scanf("%d",&a[i]);
			if(!M.count(a[i]))M[a[i]]=++cnt;
			inq[M[a[i]]]=0;
        }
        for(int i=1;i<=n;i++)a[i]=M[a[i]];
		while(!Q.empty())Q.pop(); 
        for(int i=n;i;i--)nxt[i]=lst[a[i]],lst[a[i]]=i;
        for(int i=1;i<=n;i++){
            if(inq[a[i]]){Q.push(make_pair(nxt[i],a[i]));continue;}
            if(k){ans++;Q.push(make_pair(nxt[i],a[i]));inq[a[i]]=1;k--;}
            else{
                while(!inq[Q.top().second])Q.pop();
                inq[Q.top().second]=0; Q.pop();
                ans++; Q.push(make_pair(nxt[i],a[i]));
                inq[a[i]]=1;
            }
        }printf("%d\n",ans);
    }return 0;
}

/*
    题目大意：给出一个序列，问有多少个区间的区间和是区间每个元素的倍数
    题解：区间和是倍数说明，区间和是区间每个元素的最小公倍数的倍数，
    所以我们n方枚举区间，计算区间和的同时计算公倍数，判断即可。
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=2005;
int t,n,a[N];
LL GCD(LL a,LL b){return b==0?a:GCD(b,a%b);}
int main(){
	scanf("%d", &t);
	while(t--){
		long long ma = 0;
		scanf("%d", &n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			ma+=a[i];
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			long long m=0,lcm=1;
			for(int j=i;j<=n;j++){
				m+=a[j];
				lcm=lcm/GCD(a[j],lcm)*a[j];
				if(lcm>ma)break;
				if(m%lcm==0)ans++;
			}
		}printf("%d\n",ans);
	}return 0;
}

/*
    题目大意：给出一个回文数的长度和数字和，问所能构成的最大的合法回文数，
    如果不存在则输出-1
    题解：基本策略是从外向里贪心，分奇偶考虑，同时特判无解的特殊情况
    以及长度为1时候的特殊情况
*/
#include <cstdio>
#include <algorithm>
#include <cstring> 
using namespace std;
int T,s,l,a[1000100];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&l,&s);
        memset(a,0,sizeof(a));
        if(9*l<s||s==1&&l>1){puts("-1");continue;}
        if(l%2==0){
            l/=2;
            if(s%2)puts("-1");
            else{
                s/=2;
                for(int i=1;i<=l;i++){
                    a[i]+=s;
                    if(a[i]>9)s=a[i]-9,a[i]=9;
                    else break;
                }
                for(int i=1;i<=l;i++)printf("%d",a[i]);
                for(int i=l;i;i--)printf("%d",a[i]);
                puts("");
            }
        }else{
            l/=2;
            if(s%2)a[l+1]=1;
            s/=2;
            for(int i=1;i<=l;i++){
                a[i]+=s;
                if(a[i]>9)s=a[i]-9,a[i]=9;
                else{s=0;break;}
            }if(s)a[l+1]+=s*2;
            for(int i=1;i<=l+1;i++)printf("%d",a[i]);
            for(int i=l;i;i--)printf("%d",a[i]);
            puts("");
        }
    }
    return 0;
}

/*
    题目大意：给出两堆石子，两人取石子策略为从任意堆取一个石子或者从两堆各取一个石子，
    没有石子可以取的人为输。
    题解：我们发现如果两个石子堆都是偶数则为必败态，因为后手一定可以保持其双偶状态，
    最后到0,0为败，其余状态均可以通过一步操作获得，因此为必胜态。
*/
#include <bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&a,&b);
		if(a%2==1||b%2==1)puts("hasan");
		else puts("abdullah");
	}return 0;
}

/*
    题目大意：给出一个带空格的字符串，可以通过空格将这个字符串分段
    使得分段之后的字符串长度相等，问是否能打到要求
    题解：我们在字符串后面补一个空格，同时记录各个空格的位置得到一个数列，
    那么题目转化为是否存在一个首项小于n/2，并且末项为n的等差数列。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,cnt,d[200010],mark[200010];
char s[200010];
int main(){
    scanf("%d",&T);
    gets(s);
    while(T--){
        gets(s+1);
        memset(mark,0,sizeof(mark));
        memset(d,0,sizeof(d));
        int n=strlen(s+1); 
        for(int i=1;i<=n;i++){
            if(s[i]=='' '')mark[i]=1;
        }mark[n+1]=1;
        n++; 
        int flag=0;
        for(int i=1;i*2<=n;i++)if(n%i==0&&mark[i]){
        	int t=i,p=1;
        	for(int j=t;j<=n;j=j+t){
        		if(!mark[j]){p=0;break;}
        	}if(p){flag=1;break;}
		} 
		if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}

/*
    题目大意：一个区间的价值被定义为这个区间的数字根据下标奇加偶减得到的答案，
    求给出序列的两个不相交的区间的最大的价值差的绝对值
    题解：首先维护正向偶项结尾包含自身的最大最小值和奇项结尾包含自身的最大最小值，
    对这些最大最小值求一个前缀极值，就是前缀最大最小值，
    考虑反向求前缀极值，因为反向的奇偶项特殊性导致最靠前的一项永远是奇数项，
    因此只要维护奇数向的包含当前位置的后缀极值即可，同理，求完前缀极值就是前缀最大最小
    对于题目要求的不相交区间，考虑枚举端点，那么端点处分割的前后缀极值均已知，
    可组合计算极值更新答案。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=100010;
int n,T;
LL a[N],mx[2][N],mn[2][N],l[2][N],r[2][N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(mx,0,sizeof(mx));
        memset(mn,0,sizeof(mn));
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        mx[1][1]=a[1]; 
        mn[1][1]=a[1]; 
        for(int i=2;i<=n;i++){
            mx[1][i]=max(a[i],mx[0][i-1]+a[i]);
            mx[0][i]=max(mx[1][i-1]-a[i],a[i-1]-a[i]);
            mn[1][i]=min(a[i],mn[0][i-1]+a[i]);
            mn[0][i]=min(mn[1][i-1]-a[i],a[i-1]-a[i]);
        }l[0][1]=a[1]; l[1][1]=a[1];
        for(int i=2;i<=n;i++){
            l[0][i]=max(l[0][i-1],mx[0][i]);
            l[0][i]=max(l[0][i],mx[1][i]);
            l[1][i]=min(l[1][i-1],mn[0][i]);
            l[1][i]=min(l[1][i],mn[1][i]);
        }
        for(int i=n;i;i--){
            r[0][i]=max(a[i],a[i]-r[1][i+1]);
            r[1][i]=min(a[i],a[i]-r[0][i+1]);
        }
        for(int i=n-1;i;i--){
            r[0][i]=max(r[0][i],r[0][i+1]);
            r[1][i]=min(r[1][i],r[1][i+1]);
        }
        LL ans=abs(a[1]-a[2]);
        for(int i=1;i<n;i++){
            ans=max(ans,abs(l[0][i]-r[1][i+1]));
            ans=max(ans,abs(l[1][i]-r[0][i+1]));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

/*
    题目大意：给出一个有向图，求出其全局最短路，如果存在负环，则输出-inf
    题解：首先，如果图中不存在负权边，那么最短路即为最小正权边，
    否则利用spfa判断负环，首先将所有点入队，等价于建立超级源点，
    然后依次出队进行运算，若某点入队n次或者其距离值小于距离最小可能值，
    说明存在负环，距离最小可能值通过输入时累加负权边获得。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=2010,M=5010;
int v[M<<1],w[M<<1],g[N],nxt[M<<1],cnt[N],in[N],ed;
LL d[N],dsum;
int q[N*N]; int h,t;
void add_edge(int x,int y,int z){
    v[++ed]=y; w[ed]=z; nxt[ed]=g[x]; g[x]=ed;
}
void add(int x,LL y){
    if(y>=d[x])return;d[x]=y;
    if(!in[x]){
        in[x]=1; cnt[x]++;
        q[++t]=x; 
    }
}
int T,n,m;
bool spfa(){
    int i,x; t=0;
    for(i=h=1;i<=n;i++)d[i]=0,in[i]=1,cnt[i]=1,q[++t]=i;
    while(h!=t+1){
		for(i=g[x=q[h++]],in[x]=0;i;i=nxt[i]){
        	add(v[i],d[x]+w[i]);
        	if(cnt[v[i]]>n||d[v[i]]<dsum)return 1;
        }
    }return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
    	dsum=0;
        scanf("%d%d",&n,&m);
        memset(g,ed=0,sizeof(g));
        LL ans=0x3f3f3f3f3f3f3f3f;        
        for(int i=1;i<=m;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add_edge(x,y,z);
            ans=min(1LL*z,ans);
            if(z<0)dsum+=z;
        }
        if(ans>=0)printf("%d\n",ans);
        else{
            if(spfa())puts("-inf");
            else{
                for(int i=1;i<=n;i++)ans=min(ans,d[i]);
                printf("%d\n",ans);
            }
        }
    }return 0;
}

/*
    题目大意：将至多18个包含0在内的非负整数两两求差，得到差值序列，
    现已知差值序列，求原数列的可能值
    题解：首先我们可以确定最大的数值mx，那么除去0，需要确立剩余16个数字，
    我们将所有差值标记c[diff]++,如果一个差值diff满足c[diff]=1&&c[mx-diff]=1,
    那么说明要么存在一个点在diff位置，要么在mx-diff位置，
    这是一个二叉分治的搜索操作，每次确定一个点，就将其与所有确定点的差值序列
    从c数组中删去，当确定其不合法时回溯，因为要保证解存在，
    所以我们可以通过下个点的两个位置放置均不合法来判定当前放置点不合法。
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,n,m,flag=0,a[400],b[20],c[1000010];
bool cmp(int a,int b){return a>b;} 
void dfs(int x,int pos){
    int i=pos,p=1;
	if(x>n){flag=1;return;}
	for(;i<m;i++)if(c[a[i]]&&c[a[0]-a[i]])break;
	for(int j=1;j<x;j++)if(--c[abs(a[i]-b[j])]<0)p=0;
	if(p){b[x]=a[i];dfs(x+1,pos+1);if(flag)return;}
    for(int j=1;j<x;j++)c[abs(a[i]-b[j])]++; p=1;
	for(int j=1;j<x;j++)if(--c[abs(a[0]-a[i]-b[j])]<0)p=0;
	if(p){b[x]=a[0]-a[i];dfs(x+1,pos+1);if(flag)return;}
	for(int j=1;j<x;j++)c[abs(a[0]-a[i]-b[j])]++;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        m=n*(n-1)/2;
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
            c[a[i]]++;
        }sort(a,a+m,cmp);
        b[1]=0; b[2]=a[0];
        c[a[0]]--; flag=0; dfs(3,1);
        sort(b+1,b+n+1);
        for(int i=1;i<n;i++)printf("%d ",b[i]);
        printf("%d\n",b[n]);
    }return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int T, n;
char s[maxn];
int a[maxn];

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d", &n);
    memset(a, 0, sizeof a);
    for(int i = 1; i <= n; i ++) {
      int x;
      scanf("%s%d", s, &x);
      a[x] ++;
    }
    int mx = 0;
    for(int i = 11111; i <= 99999; i ++) {
      mx = max(mx, a[i]);
    }
    for(int i = 11111; i <= 99999; i ++) {
      if(a[i] == mx) {
        printf("%d\n", i);
        break;
      }
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int T, n;
char s[maxn], t[maxn];
int cnt[500];

int main() {
  scanf("%d", &T);
  while(T --) {
    memset(cnt, 0, sizeof cnt);
    scanf("%s%s", s, t);
    int lens = strlen(s);
    int lent = strlen(t);
    
    for(int i = 0; t[i]; i ++) {
      cnt[t[i]] ++;
    }
    
    int ans = -1;
    for(int i = 0; i < lens; i ++) {
      if(cnt[s[i]] == 0) break;
      ans = i;
      cnt[s[i]] --;
    }
    printf("%d\n", ans + 1);
    
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int T, n;
int a, b, c;

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d%d%d", &a, &b, &c);
    if(a < b && a < c) {
      printf("First\n");
    }
    if(b < a && b < c) {
      printf("Second\n");
    }
    if(c < a && c < b) {
      printf("Third\n");
    }
    
  }
  return 0;
}

#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
typedef long long LL;

LL n,m;
LL p = 1e9 + 7;

const int maxn = 1e5 + 10;
LL f[maxn];

//******************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
  if(a==0&&b==0) return -1;//无最大公约数
  if(b==0){x=1;y=0;return a;}
  long long d=extend_gcd(b,a%b,y,x);
  y-=a/b*x;
  return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{
  long long x,y;
  long long d=extend_gcd(a,n,x,y);
  if(d==1) return (x%n+n)%n;
  else return -1;
}


LL C(LL n, LL m)
{
  long long A = f[n];
  long long B = f[n - m] * f[m] % p;
  long long C = mod_reverse(B, p);
  return A * C % p;
}

int main()
{
  int T;
  f[0] = 1;
  for(long long i = 1; i < maxn; i ++) {
    f[i] = f[i - 1] * i % p;
  }
  scanf("%d", &T);
  while(T--)
  {
    scanf("%lld%lld", &n, &m);
    if(n == 0) {
      printf("0\n");
      continue;
    }
    printf("%lld\n", C(n - 1, m) * 2 % p);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int T, n;
char s[maxn], t[maxn];
int cnt[500];

int main() {
  scanf("%d", &T);
  while(T --) {
    long long a, b;
    cin >> a >> b;
    cout << a + b - 1 << endl;
    
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int T, n, k;
int a[maxn], b[maxn], nx[maxn], pos[maxn];
int s[4 * maxn];
int f[maxn];

int lsh(int x) {
  int L = 1, R = n;
  while(L <= R) {
    int mid = (L + R) / 2;
    if(b[mid] > x) R = mid - 1;
    else if(b[mid] < x) L = mid + 1;
    else return mid;
  }
  return 0;
}

void build(int l, int r, int rt) {
  s[rt] = 0;
  if(l == r) return;
  int mid = (l + r) / 2;
  build(l, mid, 2 * rt);
  build(mid + 1, r, 2 * rt + 1);
}

void update(int p, int val, int l, int r, int rt) {
  if(l == r) {
    s[rt] = val;
    return;
  }
  int mid = (l + r) / 2;
  if(p <= mid) update(p, val, l, mid, 2 * rt);
  else update(p, val, mid + 1, r, 2 * rt + 1);
  s[rt] = max(s[2 * rt], s[2 * rt + 1]);
}

int work(int l, int r, int rt) {
  if(l == r) return l;
  int mid = (l + r) / 2;
  if(s[2 * rt] > s[2 * rt + 1]) return work(l, mid, 2 * rt);
  else return work(mid + 1, r, 2 * rt + 1);
}

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &a[i]);
      b[i] = a[i];
      f[i] = 0;
      pos[i] = n + 1;
    }
    sort(b + 1, b + 1 + n);
    for(int i = 1; i <= n; i ++) {
      a[i] = lsh(a[i]);
    }
    for(int i = n; i >= 1; i --) {
      nx[i] = pos[a[i]];
      pos[a[i]] = i;
    }
    build(1, n, 1);
    int ans = 0;
    int now = 0;
    for(int i = 1; i <= n; i ++) {
      if(f[a[i]]) {
        update(a[i], nx[i], 1, n, 1);
        continue;
      }
      ans ++;
      if(now < k) {
        f[a[i]] = 1;
        now ++;
        update(a[i], nx[i], 1, n, 1);
      } else {
        int del = work(1, n, 1);
        update(del, 0, 1, n, 1);
        update(a[i], nx[i], 1, n, 1);
        f[del] = 0;
        f[a[i]] = 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2000 + 10;
int T;
int n, k;
long long a[maxn];
long long sum[maxn][maxn];
long long lcm[maxn][maxn];
long long limit = 2000LL * 1e9;

long long gcd(long long a, long long b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

long long LCM(long long a, long long b) {
  long long A = a / gcd(a, b);
  long long B = b;
  
  if(A > limit / B) return -1;
  return A * B;
}

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%lld", &a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
      for(int j = i; j <= n; j ++) {
        sum[i][j] = sum[i][j - 1] + a[j];
        if(j == i) lcm[i][j] = a[j];
        else lcm[i][j] = LCM(a[j], lcm[i][j - 1]);
        if(lcm[i][j] > limit || lcm[i][j] == -1) break;
        if(sum[i][j] % lcm[i][j] == 0) ans ++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int T;
int n, s;
int ans[maxn];

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &s);
    if(n % 2 == 0) {
      if(s % 2 || s > n * 9) printf("-1\n");
      else {
        s = s / 2;
        for(int i = 0; i < n / 2; i ++) {
          if(s >= 9) ans[i] = 9, s -= 9;
          else ans[i] = s, s = 0;
        }
        for(int i = 0; i < n / 2; i ++) {
          printf("%d", ans[i]);
        }
        for(int i = n / 2 - 1; i >= 0; i --) {
          printf("%d", ans[i]);
        }
        printf("\n");
      }
    } else {
      int p = -1;
      for(int i = 0; i <= 9; i ++) {
        if((s - i) % 2 != 0) continue;
        if((s - i) > 9 * (n - 1)) continue;
        p = i;
        break;
      }
      if(p == -1) {
        printf("-1\n");
        continue;
      }
      s = (s - p) / 2;
      for(int i = 0; i < n / 2; i ++) {
        if(s >= 9) ans[i] = 9, s -= 9;
        else ans[i] = s, s = 0;
      }
      if(ans[0] == 0) {
        printf("-1\n");
        continue;
      }
      for(int i = 0; i < n / 2; i ++) {
        printf("%d", ans[i]);
      }
      printf("%d", p);
      for(int i = n / 2 - 1; i >= 0; i --) {
        printf("%d", ans[i]);
      }
      printf("\n");
    }
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;

int T, n, m;
int dp[1010][1010];

void init() {
  for(int i = 0; i <= 1000; i ++) {
    dp[0][i] = i % 2;
    dp[i][0] = i % 2;
  }
  for(int i = 1; i <= 1000; i ++) {
    for(int j = i; j <= 1000; j ++) {
      if(dp[i - 1][j] == 0
         || dp[i][j - 1] == 0
         || dp[i - 1][j - 1] == 0) {
        dp[i][j] = 1;
        dp[j][i] = 1;
      } else {
        dp[i][j] = 0;
        dp[j][i] = 0;
      }
    }
  }
  for(int i = 0; i <= 10; i ++) {
    for(int j = i; j <= 10; j ++) {
      printf("%d %d %d\n", i, j, dp[i][j]);
    }
  }
}

int main() {
 // init();
  scanf("%d", &T);
  while(T --) {
    int ans;
    scanf("%d%d", &n, &m);
    if(n > m) swap(n, m);
    if(n % 2) ans = 1;
    else ans = m % 2;
    if(ans) printf("hasan\n");
    else printf("abdullah\n");
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int T;
char s[maxn];
int a[maxn];
int L, R;

int work(int x) {
  int now;
  for(now = L + x; now <= R; now += x) {
    if(now > R + 1) return 0;
    if(now == R + 1) return 1;
    if(a[now - 1] == 1 && a[now] == 0) {
      while(a[now] == 0) now ++;
    }
    else return 0;
  }
  if(now != R + 1) return 0;
  return 1;
}

int main() {
  scanf("%d", &T);
  getchar();
  while(T --) {
    gets(s);
    int len = strlen(s);
    for(int i = 0; i < len; i ++) {
      if(s[i] == '' '') a[i] = 0;
      else a[i] = 1;
    }
    L = 0, R = len - 1;
    while(a[L] == 0) L ++;
    while(a[R] == 0) R --;
    //printf("%d %d\n", L, R);
    if(R < L) {
      while(1) {}
      printf("YES\n");
      continue;
    }
    int ans = 0;
    for(int i = 1; i < len; i ++) {
      ans = work(i);
    //  if(ans) printf("debug %d\n", i);
      if(ans) break;
    }
    if(ans) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int T, n;
long long a[maxn];
long long L[2][maxn][2];
long long R[2][maxn][2];
long long ll[2][maxn];
long long rr[2][maxn];

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%lld", &a[i]);
    }
    L[0][1][0] = a[1];
    L[1][1][0] = a[1];
    L[0][2][0] = a[2];
    L[0][2][1] = a[1] - a[2];
    L[1][2][0] = a[2];
    L[1][2][1] = a[1] - a[2];
    for(int i = 3; i <= n; i ++) {
      /* min */
      L[0][i][0] = min(a[i], L[0][i - 1][1] + a[i]);
      L[0][i][1] = L[0][i - 1][0] - a[i];
      /* max */
      L[1][i][0] = max(a[i], L[1][i - 1][1] + a[i]);
      L[1][i][1] = L[1][i - 1][0] - a[i];
    }
    
    R[0][n][0] = a[n];
    R[0][n][1] = -a[n];
    R[1][n][0] = a[n];
    R[1][n][1] = -a[n];
    for(int i = n - 1; i >= 1; i --) {
      /* min */
      R[0][i][0] = min(a[i], a[i] + R[0][i + 1][1]);
      R[0][i][1] = min(-a[i], -a[i] + R[0][i + 1][0]);
      /* max */
      R[1][i][0] = max(a[i], a[i] + R[1][i + 1][1]);
      R[1][i][1] = max(-a[i], -a[i] + R[1][i + 1][0]);
    }
    
    ll[0][1] = a[1];
    ll[1][1] = a[1];
    for(int i = 2; i <= n; i ++) {
      /* min */
      ll[0][i] = min(ll[0][i - 1], min(L[0][i][0], L[0][i][1]));
      /* max */
      ll[1][i] = max(ll[1][i - 1], max(L[1][i][0], L[1][i][1]));
    }
    
    rr[0][n] = a[n];
    rr[1][n] = a[n];
    for(int i = n - 1; i >= 1; i --) {
      /* min */
      rr[0][i] = min(rr[0][i + 1], R[0][i][0]);
      /* max */
      rr[1][i] = max(rr[1][i + 1], R[1][i][0]);
    }
    
    long long ans = 0;
    for(int i = 2; i <= n; i ++) {
      ans = max(ans, abs(ll[0][i - 1] - rr[1][i]));
      ans = max(ans, abs(ll[1][i - 1] - rr[0][i]));
    }
    printf("%lld\n", ans);
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 6000 * 1e6;
const int maxn = 1e5 + 10;
int T, n, m;
int h[maxn], v[maxn], nx[maxn];
long long w[maxn];
int sz;
long long dis[maxn];
int f[maxn], cnt[maxn];
long long g[2100][2100];
long long sum;
long long ans;

void add(int a, int b, long long c) {
  v[sz] = b;
  w[sz] = c;
  nx[sz] = h[a];
  h[a] = sz ++;
}

void spfa() {
  int fail = 0;
  for(int i = 0; i <= n; i ++) {
    dis[i] = INF;
    f[i] = 0;
    cnt[i] = 0;
  }
  queue<int> q;
  dis[0] = 0;
  f[0] = 1;
  q.push(0);
  while(!q.empty()) {
    int first = q.front();
    q.pop();
    f[first] = 0;
    cnt[first] ++;
    if(cnt[first] == n + 1) {
      fail = 1;
      break;
    }
    if(dis[first] < sum) {
      fail = 1;
      break;
    }
    for(int i = h[first]; i != -1; i = nx[i]) {
      if(dis[first] + w[i] < dis[v[i]]) {
        dis[v[i]] = dis[first] + w[i];
        if(f[v[i]] == 0) {
          f[v[i]] = 1;
          q.push(v[i]);
        }
      }
    }
  }
  if(fail) {
    printf("-inf\n");
  } else {
    long long mn = INF;
    for(int i = 1; i <= n; i ++) {
      mn = min(mn, dis[i]);
    }
    if(mn == 0) printf("%lld\n", ans);
    else printf("%lld\n", min(ans, mn));
  }
}

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i ++) {
      h[i] = -1;
    }
    sz = 0;
    for(int i = 0; i <= n; i ++) {
      for(int j = 0; j <= n; j ++) {
        g[i][j] = INF;
      }
    }
    for(int i = 1; i <= m; i ++) {
      int a, b;
      long long c;
      scanf("%d%d%lld", &a, &b, &c);
      g[a][b] = min(c, g[a][b]);
    }
    sum = 0;
    ans = INF;
    for(int i = 1; i <= n; i ++) {
      for(int j = 1; j <= n; j ++) {
        if(g[i][j] == INF) continue;
        add(i, j, g[i][j]);
        ans = min(ans, g[i][j]);
        if(g[i][j] < 0) sum += g[i][j];
      }
    }
    for(int i = 1; i <= n; i ++) {
      add(0, i, 0);
    }
    spfa();
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int T, n, m;
int d[maxn];
int ans[maxn];
int p[maxn];
int suc;

void dfs(int x, int y) {
  if(x == n) {
    int ok = 1;
    for(int i = 0; i < m; i ++) {
      if(p[d[i]]) ok = 0;
    }
    if(ok) suc = 1;
    return;
  }
  if(p[d[y]] == 0) {
    dfs(x, y - 1);
    return;
  }
  for(int t = 0; t < 2; t ++) {
    int fail = 0;
    if(t == 0) ans[x] = d[y];
    else ans[x] = ans[1] - d[y];
    for(int i = 0; i < x; i ++) {
      if(p[abs(ans[x] - ans[i])] == 0) {
        fail = 1;
      }
    }
    if(fail) continue;
    for(int i = 0; i < x; i ++) {
      p[abs(ans[x] - ans[i])] --;
    }
    dfs(x + 1, y - 1);
    if(suc) return;
    for(int i = 0; i < x; i ++) {
      p[abs(ans[x] - ans[i])] ++;
    }
  }
}

int main() {
  scanf("%d", &T);
  while(T --) {
    scanf("%d", &n);
    m = n * (n - 1) / 2;
    for(int i = 0; i < m; i ++) {
      scanf("%d", &d[i]);
      p[d[i]] ++;
    }
    sort(d, d + m);
    ans[0] = 0;
    ans[1] = d[m - 1];
    p[ans[1]] --;
    suc = 0;
    dfs(2, m - 2);
    sort(ans, ans + n);
    for(int i = 0; i < n; i ++) {
      printf("%d", ans[i]);
      if(i < n - 1) printf(" ");
      else printf("\n");
    }
    for(int i = 0; i < m; i ++) {
      if(p[d[i]]) {
        while(1) {}
      }
    }
  }
  return 0;
}